BOJ 1012 · 유기농 배추

알고리즘 분류 : DFS

배추 밭에 놓아야 하는 배추흰지렁이의 마릿수를 구해야 한다. 배추흰지렁이는 하나의 배추 그룹에 한 마리만 놓으면, 최소 마릿수가 된다. 즉, 이 문제는 배추 그룹의 수를 세는 플러드 필 문제이다. 배추가 인접한 상하좌우로 연결되면, 이것은 하나의 배추 그룹이 된다.

• 우선 N*M 사이즈의 배열 A를 만들고 모든 좌표를 0으로 둔다.
• 입력으로 주어지는 배추의 좌표 (X, Y)를 배열 A에 1로 둔다.
• N*M 사이즈의 맵을 DFS를 통해 모든 곳을 방문할 때까지 완전 탐색한다.
• DFS로 다음 좌표를 이동할 때, 배추(1)로만 이동한다.
• 테스트케이스가 여러 개 주어지므로, 초기화가 매번 필요하다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>

int m, n, k, ans;
int a[51][51];
bool check[51][51];
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 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 >= n || ny < 0 || ny >= m) continue;
        if (a[nx][ny] && !check[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

void solve() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (a[i][j] && !check[i][j]) {
                dfs(i, j);
                ans++;
            }
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        memset(check, 0, sizeof(check));
        memset(a, 0, sizeof(a));
        scanf("%d %d %d", &m, &n, &k);
        for (int i=0; i<k; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            a[y][x] = 1;
        }
        solve();
        printf("%d\n", 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 >= n or ny < 0 or ny >= m:
            continue
        if a[nx][ny] and not check[nx][ny]:
            dfs(nx, ny)

def solve():
    ans = 0
    for i in range(n):
        for j in range(m):
            if a[i][j] and not check[i][j]:
                dfs(i, j)
                ans += 1
    print(ans)

for _ in range(int(input())):
    m, n, k = map(int, input().split())
    a = [[0]*m for _ in range(n)]
    check = [[False]*m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        a[y][x] = 1
    solve()

---

참고

• 백준 온라인 저지 : BOJ 1012