백준|1012번|유기농 배추

문제설명
배추를 키우는 밭에서 해충 제거를 위해 배추지렁이를 키우려고 한다. 배추지렁이는 서로 인접한 배추 사이만 이동할 수 있다고 할 때, 밭의 크기와 배추의 위치를 입력받고 배추지렁이가 몇마리 필요한지 출력하는 문제입니다.

작동 순서
1. 배추밭의 크기와 배추의 개수를 입력받습니다.
2. 입력받은 배추밭의 크기에 따라 2차원 boolean 배열 field와 visited를 생성합니다. 2개를 생성하는 이유는 하나는 방문처리용으로 이용하고 하나는 배추의 위치를 입력받기 위함입니다.
3. 배추의 위치를 입력받고 field에서 입력받은 위치를 true로 바꿔줍니다.
4. DFS를 이용하여 각 위치를 방문하고 방문한 곳을 위치처리해줍니다.
5. 방문한 위치에 배추가 있을 경우 그 주변 위치도 모두 방문하고 이를 반복합니다.
6. DFS가 새로운 배추 지역을 발견할 때마다 필요한 지렁이의 개수를 하나 더해줍니다.​
7. 배추밭을 모두 탐색하고 나면 필요한 지렁이의 개수를 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준_1012번_유기농배추 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static boolean[][] field;
    static boolean[][] visited;
    static int worm;
    static void inputCabbage(int num) throws IOException {
        for(int i=0;i<num;i++){
            String[] input=br.readLine().split(" ");
            field[Integer.parseInt(input[0])][Integer.parseInt(input[1])]=true;
        }
    }

    static void Search(int h, int v, int count){
        int[][] move={{-1,0},{1,0},{0,-1},{0,1}};
        visited[h][v]=true;
        if(field[h][v]==true){
            if(count==1) worm++;
            for(int i=0;i<4;i++){
                if(h+move[i][0]>=0&&v+move[i][1]>=0&&h+move[i][0]< field.length&&v+move[i][1]<field[0].length){
                    if(field[h+move[i][0]][v+move[i][1]]==true&&visited[h+move[i][0]][v+move[i][1]]==false){
                        Search(h+move[i][0],v+move[i][1], count+1);
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        int T=Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            String[] input=br.readLine().split(" ");
            int M=Integer.parseInt(input[0]), N=Integer.parseInt(input[1]), K=Integer.parseInt(input[2]);
            field=new boolean[M][N];
            visited=new boolean[M][N];
            worm=0;
            inputCabbage(K);
            for(int m=0;m<M;m++){
                for(int n=0;n<N;n++){
                    if(visited[m][n]==false) Search(m, n, 1);
                }
            }
            System.out.println(worm);
        }
    }
}

후기
유기농 배추 문제를 풀어보았는데 그래프 탐색 문제는 아직 많이 접해보지 않아서 어려움이 있었지만 결국 하다보니 풀 수 있었습니다. 앞으로도 꾸준히 다양한 유형의 문제들을 접해봐야 할 것 같습니다.