[C++] 백준 4963번 : 섬의 개수 풀이

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

이 문제는 BFS와 DFS 모두 풀 수 있는 문제이다. 글쓴이는 DFS를 이용하여 이 문제를 풀어보았다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stdbool.h>
#include <vector>
#include <cstring>

using namespace std;

const int MN = 51;

int map[MN][MN]; //인접행렬
bool vst[MN][MN]; //방문 여부
int di[8] = {1, 0, 0, -1, 1, -1, 1, -1}; //8가지 방향으로 이동을 나타냄
int dj[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int w, h;
void dfs(int i, int j) {
    vst[i][j] = true; //방문 체크
    for(int d = 0; d < 8; d++) { //8가지 방향을 탐색
        int ni = i + di[d]; //다음 i좌표
        int nj = j + dj[d]; //다음 j좌표
        if(0 <= ni && ni < h && 0 <= nj && nj < w) { //지도를 벗어나는지 확인
            if(!vst[ni][nj] && map[ni][nj]) { //방문 여부와 땅인지 여부 확인
                dfs(ni, nj); //재귀로 DFS 탐색
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    while(true) { //0을 입력받을 때까지 반복
        cin >> w >> h;
        if(w == 0 && h == 0) break; //0이 두 개 입력될 경우 종료
        memset(map, 0, sizeof(map)); //테스트케이스마다 초기화
        memset(vst, 0, sizeof(vst)); //테스트케이스마다 초기화
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j]; //지도 입력
            }
        }
        int cnt = 0;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(map[i][j] && !vst[i][j]) { //땅이고 방문하지 않은 경우 DFS 탐색
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
}

이 문제는 지도를 주어졌을 때 상하좌우 대각선으로 땅이 이어져 있다고 할 때 분리된 섬의 개수를 구하는 문제이다. 우리는 x, y좌표 형식으로 문제를 입력받기 때문에 위 코드의 di, dj 배열과 같이 8가지 방향을 나타낼 수 있다. 그림으로 나타내면 다음과 같이 나타낼 수 있다.

i, j에서 8가지 방향의 좌표를 더해 ni, nj 좌표를 구한다. 이때 지도를 벗어나는지를 확인해준다. 그렇지 않으면 Out of Bounds 에러가 발생할 수 있다.  그 다음 방문 여부와 땅인지의 여부를 확인하여 DFS 탐색을 계속한다. 이때 지도에서 땅인 부분의 DFS 횟수가 곧 섬의 개수인 것을 알 수 있다. 이전에 풀은 연결 요소의 개수와 구하는 방식이 비슷한 것을 알 수 있다. 차이점은 인접리스트 형식이 아니라 좌표형식으로 주어진 입력을 활용하여 좌표를 이동하며 DFS를 한다는 것이다.