BOJ 4963 · 섬의 개수

알고리즘 분류 : DFS  

섬의 개수를 세는 문제다. 섬은 인접한 땅으로 이루어져 있고, 인접의 기준은 센터를 중심으로 8방향(상하좌우대각선)으로 한 칸씩 떨어진 곳이다. 4방향 인접 문제에서 방향만 추가해서 구현하면 된다. 비슷한 문제는 BOJ 2667번 '단지번호붙이기'이다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>

int w, h;
int a[51][51];
bool check[51][51];
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

void dfs(int x, int y) {
    check[x][y] = true;
    for (int i=0; i<8; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= h || nx < 0 || ny >=w) continue;
        if (!a[nx][ny] || check[nx][ny]) continue;
        dfs(nx, ny);
    }
}

int main() {
    while (true) {
        scanf("%d %d", &w, &h);
        if (!w) break;
        memset(check, false, sizeof(check));
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        int cnt = 0;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (a[i][j] && !check[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

---

Python 3 소스코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

dx = (-1, -1, -1, 0, 1, 1, 1, 0)
dy = (-1, 0, 1, 1, 1, 0, -1, -1)

while True:
    w, h = map(int, input().split())
    if not w:
        break
    a = [list(map(int, input().split())) for _ in range(h)]
    check = [[False]*w for _ in range(h)]

    def dfs(x, y):
        check[x][y] = True
        for i in range(8):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if a[nx][ny] == 1 and check[nx][ny] is False:
                dfs(nx, ny)

    cnt = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == 1 and check[i][j] is False:
                dfs(i, j)
                cnt += 1
    print(cnt)

---

참고

• 백준 온라인 저지 : BOJ 4963
• 단지번호붙이기