[백준/C++] 4963번 섬의 개수

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

4963번: 섬의 개수

문제 분석

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다.

정수 1은 섬(land)이고, 정수 0은 바다(sea)로 표현된다.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력으로는 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 지도의 너비 W와 높이 H가 주어진다. 둘 다 50보다 작거나 같다. 그리고 두번째 줄부터는 지도가 주어진다.

마지막 입력으로는 너비와 높이가 각각 0으로 주어질 때,

각 테스트 케이스에 대해, 섬의 개수를 출력하면 된다.

​코드

#include<iostream>

using namespace std;

int w,h,cnt;
int map[51][51]; // 지도
bool visited[51][51]; // 탐색 여부

//방향 벡터(상 하 좌우 대각선)
int dx[8] = { 1,1,0,-1,-1,-1,0,1 }; 
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


void dfs(int y, int x) {
    visited[y][x] = true;

    for (int i = 0; i < 8; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= h || nx >= w)
            continue;

        if (map[ny][nx] == 1 && visited[ny][nx] == 0) {
            visited[ny][nx] = 1;
            dfs(ny, nx);
        }
    }
}

// 여러 개의 테스트 케이스가 존재하므로 초기화 함수
void reset() {
    cnt = 0;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            map[i][j] = 0;
            visited[i][j] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (1) {
        cin >> w >> h; // w가 열, h가 행
        reset();
        if (w == 0 && h == 0) {
            break;
        }
        else {
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    cin >> map[i][j];
                }
            }
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] ==1 && visited[i][j] ==false) {
                        visited[i][j] = true;
                        dfs(i, j);
                        cnt++;
                    }
                }
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

문제 풀이

이 문제는 기본적인 dfs(깊이 우선 탐색)로 해결 가능한 문제이다.

입력이 0 0(종료조건)이 아닐 때

-> 지도를 입력받고 -> i행 j열이 1이면서 (=섬) 그리고 아직 탐색하지 않은 땅을 만나면

-> 이제 방문하였으므로 방문 여부를 true로 설정하고 dfs 함수를 호출한다.

-> for문을 방향벡터의 크기만큼 돌리면서 8개의 방향을 모두 탐색한다.

-> 탐색 중 마찬가지로 섬이면서 아직 탐색되지 않은 곳을 만나면 다시 dfs를 호출하여, 방문 여부를 수정해준다.

-> dfs함수의 작동이 끝나면 cnt를 ++해줌으로써 발견한 섬의 수를 하나 증가시켜준다.

-> 탐색이 끝났다면 cnt(섬의 개수)를 출력해주면 끝이다.