BOJ 13746 · Islands

알고리즘 분류 : DFS  

주어진 맵에 존재하는 섬의 최소 개수를 구하는 문제다. 전형적인 플러드 필 문제이다.

• 맵에서 땅('L')을 시작점으로 하여 DFS 탐색을 한다.
• 구름('C')은 땅 또는 물이 될 수 있으므로, 이동 가능하다.
• 물('W')로는 이동할 수 없다.
• 모든 땅의 탐색이 끝날 때까지 진행한다.

---

C++ 소스코드

#include <cstdio>

int r, c, ans;
char a[51][51];
bool check[50][50];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    check[x][y] = true;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
        if (!check[nx][ny] && a[nx][ny] != 'W') dfs(nx, ny);
    }
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i=0; i<r; i++) scanf("%s", a[i]);
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            if (!check[i][j] && a[i][j] == 'L') {
                dfs(i, j);
                ans += 1;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

r, c = map(int, input().split())
a = [list(input().strip()) for _ in range(r)]
check = [[False]*c for _ in range(r)]
ans = 0

def dfs(x, y):
    check[x][y] = True
    for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
        nx, ny = x+dx, y+dy
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            continue
        if not check[nx][ny] and a[nx][ny] != 'W':
            dfs(nx, ny)

for i in range(r):
    for j in range(c):
        if not check[i][j] and a[i][j] == 'L':
            dfs(i, j)
            ans += 1
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 13746