[백준 1012번] 유기농 배추

문제 설명

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

알고리즘

깊이 우선 탐색(DFS, Depth-First Search)

접근 방식 및 풀이

이 문제에선 필요한 최소의 배추흰지렁이 마리 수를 물어보고 있다. 배추흰지렁이를 모든 배추마다 둘 수도 있지만 배추흰지렁이는 인접한 다른 배추로 이동할 수 있기 때문에 이어진 배추 무리당 하나의 배추흰지렁이를 두어도 모든 배추들이 해충으로부터 안전할 수 있다. 이때가 배추흰지렁이가 최소로 사용되는 경우이고 결국 이어진 배추 무리의 개수가 곧 필요한 최소의 배추흰지렁이 마리 수인 것이다.

DFS

그럼 이어진 배추 무리를 어떻게 찾을까? 이어진 배추 무리는 결국 배추 루트를 찾는 것과 같기 때문에 DFS를 사용하면 된다.

먼저 배추밭 배열을 만들고 배추가 심어진 땅(1)과 배추가 없는 땅(0)을 표시한다. 또한 이미 계산에 포함한 땅에 경우 또 계산에 포함하지 말아야하므로 이미 계산한 땅을 체크하는 배열을 만든다.

배추밭을 0,0부터 시작해서 끝까지 이동하면서 배추가 심어져 있으면서 아직 계산에 포함되지 않은 땅인 경우 DFS 함수를 실행한다. DFS 함수 내부에선 해당 땅을 체크하고(계산에 포함되었으므로) 해당 배추와 이어진 배추(위쪽, 아래쪽, 오른쪽, 왼쪽)를 찾는다. 이어진 배추의 땅이 아직 계산에 포함되지 않았을 있을 경우, 해당 땅에서 다시 DFS 함수를 호출한다. 반복되는 DFS 함수가 끝나고 밖으로 나오면 하나의 이어진 배추 무리를 찾은 것이다.

한칸씩 이동하면서 배추가 심어져 있고 아직 계산에 포함되지 않은 땅을 발견할 때마다 DFS 함수를 실행하게 되면 이어진 배추 무리의 개수를 구할 수 있다. 결국 이 값이 필요한 최소의 배추흰지렁이 마리 수와 같으므로 해당 값을 출력한다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>

void checking(int row, int col);

int fieldNum; // 배추밭 개수
int maxRow, maxCol; // 배추밭 가로 세로 길이
int cabbageNum, wormNum; // 배추 개수, 배추흰지렁이 개수
int array[50][50]; // 밭의 상태를 표현하기 위한 배열 (배추가 없는 땅 = 0, 배추가 있는 땅 = 1)
int mark[50][50]; // 계산을 한 땅을 체크하기 위한 배열
int dRow[4] = { 1, -1, 0, 0 }; // 위쪽, 아래쪽, 오른쪽, 왼쪽
int dCol[4] = { 0, 0, 1, -1 };

int main(){
    scanf("%d\n", &fieldNum);
    
    for(int i = 0; i < fieldNum; i++){ // 배추밭마다 계산
        scanf("%d %d %d\n" , &maxCol, &maxRow, &cabbageNum);
        
        for(int j = 0; j < maxRow; j++){
            for(int k = 0; k < maxCol; k++){
                array[j][k] = 0; // 배추밭 초기화
                mark[j][k] = 0; // 체크 배열 초기화
            }
        }
        
        int temRow, temCol;
        for(int j = 0; j < cabbageNum; j++){
            scanf("%d %d\n", &temCol, &temRow);
            array[temRow][temCol] = 1; // 해당하는 땅을 배추가 있는 땅으로 바꾼다
        }
        
        wormNum = 0; // 배추흰지렁이 개수 초기화
        for(int j = 0; j < maxRow; j++){
            for(int k = 0; k < maxCol; k++){
                if(array[j][k] == 1 && mark[j][k] == 0){ // 배추가 있는 땅이면서 아직 체크하지 않은 땅이면
                    wormNum++; // 배추흰 지렁이 개수를 늘린다
                    checking(j, k); // 해당 배추와 이어진 배추들은 찾아서 모두 체크한다
                }
            }
        }
        printf("%d\n", wormNum);
    }
    return 0;
}

// 이어져 있는 배추를 찾는 DFS 함수
void checking(int row, int col){
    mark[row][col] = 1; // 체크
    
    for(int i = 0; i < 4; i++){ // 위쪽, 아래쪽, 오른쪽, 왼쪽 확인
        int nextRow = row + dRow[i];
        int nextCol = col + dCol[i];
        
        if (nextRow < 0 || nextRow >= maxRow || nextCol < 0 || nextCol >= maxCol) // 해당 땅이 배추밭 범위를 벗어났다면 넘어간다.
            continue;
        
        if(array[nextRow][nextCol] == 1 && mark[nextRow][nextCol] == 0) // 해당 땅이 배추가 있고 아직 계산에 포함되지 않았다면
            checking(nextRow, nextCol); // 해당 땅으로 DFS 함수 호출
    }
}