[백준/C] 1012 - 유기농 배추

https://www.acmicpc.net/problem/1012

풀이 참고

구현 과정

DFS 사용

DFS에서는 한 지점에서 시작해 가능한 멀리, 깊게 탐색한다. 이 문제에서는 배추가 심어져 있는 땅이라면, 그 땅의 상하좌우를 살펴보며 다른 배추가 있는지를 확인해야 하기 때문에 DFS를 이용한다. 연결된 배추를 모두 찾아야지 쓸 수 있는 지렁이의 최솟값이 나오기 때문이다.

DFS 함수 내에서는 상하좌우에 대해 배추가 심어져 있는지를 판단한다.

if (x + 1 < m && field[x + 1][y] == 1)
    dfs(x + 1, y);
if (x - 1 >= 0 && field[x - 1][y] == 1)
    dfs(x - 1, y);
if (y + 1 < n && field[x][y + 1] == 1)
    dfs(x, y + 1);
if (y - 1 >= 0 && field[x][y - 1] == 1)
    dfs(x, y - 1);

오른쪽, 왼쪽, 위쪽, 아래쪽에 대한 배추 확인이다.
각 if문에서 그 방향으로 한칸 더 간 값이 주어진 범위를 벗어나지 않는지, 그 칸에 배추가 있는지를 확인 한 후, 두 조건을 모두 만족하는 경우에 그 칸에 대해 dfs를 다시 재귀 호출한다.

main 함수 내에서는
1. x, y를 입력받으며 해당 땅을 배추가 심어진 땅으로 표시해준다. 즉, field[x][y] = 1을 해준다.
2. count를 0으로 초기화해둔 뒤, 가로길이 m, 세로길이 n까지 이중 for문을 사용해 순회하며 해당 땅 == 배추 심어져 있는 땅인 경우 dfs(i,j)를 호출하고, 지렁이 수++ 를 해준다.

전체 코드

#include <stdio.h>
#include <string.h>

int m, n;
int field[50][50];

int dfs(int x, int y) {
    field[x][y] = 0;
    
    if (x + 1 < m && field[x + 1][y] == 1)
        dfs(x + 1, y);
    if (x - 1 >= 0 && field[x - 1][y] == 1)
        dfs(x - 1, y);
    if (y + 1 < n && field[x][y + 1] == 1)
        dfs(x, y + 1);
    if (y - 1 >= 0 && field[x][y - 1] == 1)
        dfs(x, y - 1);

    return 0;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        int k;
        scanf("%d %d %d", &m, &n, &k);

        while (k--) {
            int x, y;
            scanf("%d %d", &x, &y);
            field[x][y] = 1;
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (field[i][j] == 1) {
                    dfs(i, j);
                    count++;
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}