[Algorithm] 백준 2468 안전 영역 - C++, DFS, BFS

2468번: 안전 영역

 

DFS 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 101;
int n;
int map[MAX][MAX];
bool visit[MAX][MAX];
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };

void SearchMap(int y, int x, const int height){
    
    for(int i = 0; i < 4; i++){
        int nextY = y + moveY[i];
        int nextX = x + moveX[i];

        if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= n)  continue;
        if(visit[nextY][nextX]) continue;
        if(map[nextY][nextX] <= height) continue;

        visit[nextY][nextX] = true;
        SearchMap(nextY, nextX, height);
    }
    
}


int main(){
    // input
    cin >> n;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < n; x++)
            cin >> map[y][x];
    
    // solve
    int maxAreaCount = 1;
    for(int height = 1; height <= 100; height++){
        int heightCount = 0;
        memset(visit, false, sizeof(visit));

        // search in this height
        for(int y = 0; y < n; y++){
            for(int x = 0; x < n; x++){
                if(!visit[y][x] && map[y][x] > height){
                    visit[y][x] = true;
                    SearchMap(y, x, height);
                    heightCount++;
                }
            }
        }

        if(heightCount == 0)    break;

        if(heightCount > maxAreaCount)
            maxAreaCount = heightCount;
    }

    cout << maxAreaCount << '\n';
}

 

BFS 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 101;
int n;
int map[MAX][MAX];
bool visit[MAX][MAX];
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };

void SearchMap(int y, int x, const int height){
    queue<pair<int, int>> q;
    q.push({y, x});
    visit[y][x] = true;

    while (!q.empty()){
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nextY = curY + moveY[i];
            int nextX = curX + moveX[i];

            if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= n)  continue;
            if(visit[nextY][nextX]) continue;
            if(map[nextY][nextX] <= height) continue;

            visit[nextY][nextX] = true;
            q.push({nextY, nextX});
        }
    }
}


int main(){
    // input
    cin >> n;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < n; x++)
            cin >> map[y][x];
    
    // solve
    int maxAreaCount = 1;
    for(int height = 1; height <= 100; height++){
        int heightCount = 0;
        memset(visit, false, sizeof(visit));

        // search in this height
        for(int y = 0; y < n; y++){
            for(int x = 0; x < n; x++){
                if(!visit[y][x] && map[y][x] > height){
                    SearchMap(y, x, height);
                    heightCount++;
                }
            }
        }

        if(heightCount == 0)    break;

        if(heightCount > maxAreaCount)
            maxAreaCount = heightCount;
    }

    cout << maxAreaCount << '\n';
}

---

처음에는 BFS로 풀이하다 안되서 DFS로 풀이하니깐 되길래 다시 BFS로 풀이하니깐 풀이가 된 문제입니다. 칸수가 100 x x100 이고 높이도 최대 100이라 전부 다 탐색을 하면 1,000,000정도라 완전탐색으로 충분히 풀이가 됩니다.

 

풀이법은 입력을 받은 뒤 for문으로 높이를 1~100까지 보면서 이 높이보다 높은 지역에서 몇번 탐색이 가능한지 세어주시면 됩니다. 만일 풀이를 잘 한거 같은데 70몇%에서 틀렸습니다가 나온다면 전부 높이가 같을때를 고려해주지 못한 것으로 보입니다. 저는 원래 maxAreaCount = -1로 초기화를 했다가 생각해보니 최소 1개의 영역은 나올 것 같아서 1로 초기화를 하고 제출을 했습니다.

DFS가 시간은 빠른데 확실히 메모리는 더 잡아먹습니다. 물론 둘 다 큰 차이라고 보기는 어렵죠.