BOJ 11123 · 양 한마리... 양 두마리...

알고리즘 분류 : DFS  

양 무리를 세는 문제이다. 전형적인 플러드 필 알고리즘이다.

• H*W 사이즈의 맵을 DFS로 탐색한다.
• 양(#)부터 시작해서, 연결된 양을 찾는다.
• 맵을 모두 탐색할 때까지 진행하여, 양 무리를 카운트한다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>

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

int 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 >= h || ny < 0 || ny >= w) continue;
        if (!check[nx][ny] && a[nx][ny] == '#') dfs(nx, ny);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int ans = 0;
        memset(check, 0, sizeof(check));
        scanf("%d %d", &h, &w);
        for (int i=0; i<h; i++) scanf("%s", a[i]);
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (!check[i][j] && a[i][j] == '#') {
                    dfs(i, j);
                    ans += 1;
                }
            }
        }
        printf("%d\h", ans);
    }
    return 0;
}

---

Python 3 소스코드

import sys
sys.setrecursionlimit(10000)

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 >= h or ny < 0 or ny >= w:
            continue
        if not check[nx][ny] and a[nx][ny] == '#':
            dfs(nx, ny)

for _ in range(int(input())):
    ans = 0
    h, w = map(int, input().split())
    a = [list(input().strip()) for _ in range(h)]
    check = [[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if not check[i][j] and a[i][j] == '#':
                dfs(i, j)
                ans += 1
    print(ans)

✓ 파이썬은 재귀 깊이 제한을 풀어줘야 한다.

---

참고

• 백준 온라인 저지 : BOJ 11123