[BOJ] 1012 - 유기농 배추

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/1012

1012번: 유기농 배추

난이도: 실버 2

사용 언어: JAVA

 

밭에 유기농 배추를 심어두었는데, 배추흰지렁이를 이용해 해충을 예방할 수 있습니다. 여기서 배추흰지렁이는 인접해있는 배추로는 이동할 수 있기 때문에, 여러 인접해있는 배추들의 경우에는 지렁이가 한 마리만 있어도 해충으로부터 보호될 수 있습니다. 여기서 인접해있다는 것은 한 배추의 상하좌우 네 방향 중에 다른 배추가 위치해있는 경우를 말합니다.

 

배추가 있는 곳은 1, 배추가 없는 곳은 0으로 표시하며, 이러한 상황에서 최종적으로 최소 몇 마리의 배추흰지렁이가 필요한지를 묻는 문제입니다. 

 

풀이

이 문제는 DFS를 이용하여 해결할 수 있습니다. DFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/65

[BOJ] 1303 - 전쟁 - 전투

 

우선 입력 값을 이용해 밭을 2차원 배열로 표현합니다. 그리고 입력 값으로부터 배추가 자라 있는 곳의 위치를 1로 표시해줍니다.

 

그리고 (0,0)에 위치한 배추부터 DFS를 이용해 탐색을 시작합니다. 이때, 한 번 검사한 배추는 0으로 바꿔주어 다시 검사하는 일이 없도록 합니다. DFS는 재귀 함수로 구현했고, DFS 함수 내에서 배열의 크기를 초과하지 않도록 조건문을 사용했습니다.

 

import java.util.Scanner;
 
class Main {
 
    static int cnt = 0;
 
    public static void dfs(int x, int y, int M, int N, int arr[][]){
        arr[x][y] = 0;
 
        if(x-1 >= 0)
            if(arr[x-1][y] == 1)
                dfs(x-1,y,M,N,arr);
        if(y+1 < N)
            if(arr[x][y+1] == 1)
                dfs(x,y+1,M,N,arr);
        if(x+1 < M)
            if(arr[x+1][y] == 1)
                dfs(x+1,y,M,N,arr);
        if(y-1 >= 0)
            if(arr[x][y-1] == 1)
                dfs(x,y-1,M,N,arr);
 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T; // 테스트 케이스의 개수
        int i,j;
 
        T = sc.nextInt();
 
        while(T > 0) {
            int M,N,K;
            M = sc.nextInt(); // 가로길이
            N = sc.nextInt(); // 세로길이
            K = sc.nextInt(); // 배추의 개수
 
            int[][] arr = new int[M][N]; // 행렬 생성
 
            for(i=0;i<K;i++){
                int x,y;
                x = sc.nextInt();
                y = sc.nextInt();
                arr[x][y] = 1;
           } // 배추의 위치 표시
 
            for(i=0;i<M;i++){
                for(j=0;j<N;j++){
                    if(arr[i][j] == 1) {
                        dfs(i, j, M, N, arr);
                        cnt++;
                    }
                }
           } // DFS 수행
 
            System.out.println(cnt);
            cnt = 0;
            T--;
        }
    }
}