BOJ 6186 · Best Grass

알고리즘 분류 : DFS, BFS  

풀덤불의 개수를 구하는 문제다. 기본적인 플러드 필 알고리즘을 구현하면 된다.

• R*C 사이즈의 맵을 탐색하면서 서로 연결된 풀(#)을 찾는다. 연결된 그룹을 하나의 덤불로 카운트한다.
• 모든 영역의 탐색이 끝날 때까지 DFS를 진행한다.

---

C++ 소스코드

#include <cstdio>

int r, c, ans;
char a[101][101];
bool check[100][100];
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] == '#') 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] == '#') {
                dfs(i, j);
                ans += 1;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

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

def bfs(i, j):
    q = deque()
    q.append((i, j))
    check[i][j] = True
    while q:
        x, y = q.popleft()
        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] == '#':
                q.append((nx, ny))
                check[nx][ny] = True

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

✓ 파이썬은 BFS로 구현했다.

---

참고

• 백준 온라인 저지 : BOJ 6186