[알고리즘 문제] 백준 4963번 섬의 개수

4963번: 섬의 개수 (acmicpc.net)

4963번: 섬의 개수

 

문제

 

2차원 그래프 상에 연결된 섬의 개수를 구하는 문제다. 그림에 제시된 상황에서는 총 3개의 섬을 찾을 수 있다.

 

아이디어

 

 1. 지도의 좌상단에서 시작하여 우하단으로 이동하며 섬을 찾는다.

 

 2. 만약 현재 탐색한 칸이 섬이면, 주변에 연결된 섬을 모두 찾는다.

      문제 데이터가 50*50으로 작기 때문에 DFS, BFS 어느 방법을 사용해도 문제없다.

      연결된 섬은 표시를 해서 다시 카운트하지 않도록 한다.

      섬 무리를 하나 찾을 때마다 카운트를 하고, 다시 세지 않도록 표시한다.

 

 3. 마지막 칸까지 탐색을 완료하면 카운트된 수가 섬의 개수다.

 

코드

// No.4963

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

int T;
int w, h;
int my_map[52][52]; // use 1~50 for convenience
int temp;

int yy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int xx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void sink(int y, int x) {
    my_map[y][x] = 0;

    for (int i : yy) {
        for (int j : xx) {
            if (my_map[y + i][x + j] == 1) {
                sink(y + i, x + j);
            }
        }
    }
}

int solve() {
    int answer = 0;

    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (my_map[i][j] == 1) {
                sink(i, j);
                answer += 1;
            }
        }
    }

    return answer;
}

int main(void) {
    while (true) {
        cin >> w >> h;

        if (w == 0 && h == 0) {
            break;
        }

        for (int j = 1; j <= h; j++) {
            for (int k = 1; k <= w; k++) {
                cin >> my_map[j][k];
            }
        }

        int answer = solve();
        cout << answer << '\n';

        memset(my_map, 0, sizeof(int) * 52 * 52);
    }
}

 

기타

2차원 그래프에서 주변 칸을 확인할 필요가 있을 때, 해당 인덱스를 배열에 저장하고 사용하면 실수를 줄일 수 있다.

// 너무 번거롭다!
if (y + 1 < w && x + 1 < h && my_map[y + 1][x + 1] == 1)
    sink(y + 1, x + 1);
else (y + 1 < w && x - 1 < 0 && my_map[y + 1][x - 1] == 1)
    sink(y + 1, x - 1);
...

 

// 간단한 버전
int yy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int xx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

for (int i : yy) {
    for (int j : xx) {
        if (y + i >= 0 && x + i >= 0
            && y + i < w && x + i < h
            && my_map[y + i][x + j] == 1
            ) {
            sink(y + i, x + j);
        }
    }
}

 

 

메모리 침범을 방지하기위해 가장자리 확인을 하는 게 번거롭다면, 몇몇 경우에서 가장자리에 안 쓰는 한 칸을 추가해서 간략화할 수 있다.

int my_map[50][50]; // 0 ~ 49

for (int i : yy) {
    for (int j : xx) {
    	// 배열 경계 검사 필요
        if (y + i >= 0 && x + i >= 0
            && y + i < w && x + i < h
            && my_map[y + i][x + j] == 1
            ) {
            sink(y + i, x + j);
        }
    }
}

 

int my_map[52][52]; // 1~50

for (int i : yy) {
    for (int j : xx) {
        // 배열을 넘어가지 않음
        if (my_map[y + i][x + j] == 1) {
            sink(y + i, x + j);
        }
    }
}

 

이번 문제는 0이 아무것도 아닌 바다를 표현해서 이 패턴이 적용 가능했다. 단, 데이터를 넣거나 읽을 때도 1부터 시작하는 인덱스를 사용해야 하니 주의한다.