[C++] 백준 알고리즘 2468번 (안전 영역)

문제

---

이번에 다뤄볼 문제는 2468번 문제 '안전 영역'입니다.

안전 영역 문제에서 연습해야하는key-point는재귀함수입니다.

 

재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다.

real_map과 map 이라는 2차원 배열을 두개 만들어 map의 값은 영역 체크가 끝나게 되면 0으로 바꿔주어 다시 탐색하지 않도록 하기 위함이고 real_map의 경우 처음 들어온 초기값을 유지하고 있는 2차원 배열입니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
int real_map[101][101];
int map[101][101];
 
int dirX[4] = { 0, 0, 1, -1 };
int dirY[4] = { 1, -1, 0, 0 };
 
int safe_count = 0;
int xx = 0, yy = 0;
 
int n, k;
 
void safe(int x, int y) {
    map[x][y] = 0;
 
    for (int i = 0; i < 4; i++) {
        xx = x + dirX[i];
        yy = y + dirY[i];
 
        if (map[xx][yy] <= k || xx<0 || yy<0 || xx>n || yy>n) continue;
        if (map[xx][yy] > k) safe(xx, yy);
    }
 
}
 
 
int main() {
 
    int count = 0;
    int max;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> real_map[i][j];
        }
    }
    max = real_map[1][1];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (real_map[i][j] > max) max = real_map[i][j];
        }
    }
 
    for (k = 0; k <= max; k++) {
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = real_map[i][j];
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] > k) {
                    count++;
                    safe(i, j);
                }
            }
        }
 
        if (count > safe_count) safe_count = count;
        count = 0;
    }
 
    cout << safe_count << endl;
 
    return 0;
}