[백준] 유기농 배추 1012번 - Java

[백준] 유기농 배추 1012번

나의 풀이

public class OrganicCabbage {
    static int[][] graph = new int[50][50];
    static int N, M, K;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            int count = 0;
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            for(int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                graph[x][y] = 1;
            }

            for(int x = 0; x < N; x++) {
                for(int y = 0; y < M; y++) {
                    if(dfs(x, y) == true) {
                        count++;
                    }
                }
            }

            sb.append(count).append("\n");
        }

        System.out.println(sb);
    }

    static boolean dfs(int x, int y) {
        if(x < 0 || y < 0 || x >= N || y >= M) {
            return false;
        }

        if(graph[x][y] == 1) {
            graph[x][y] = 0;

            dfs(x + 1, y);
            dfs(x - 1, y);
            dfs(x, y + 1);
            dfs(x, y - 1);

            return true;
        }

        return false;
    }
}

• dfs를 사용하여 접근하였다.
• 우선 dfs에서 사용하기 위해서 2차 배열과 N,M,K 를 정의해 주었다.
• 입력되는 x 좌표와 y좌표를 가지고 2차 배열의 해당 x, y 좌표의 값을 1로 만들어 연결시켜준다.
• 2차 배열의 연결이 모두 완료되면 이제 2차 배열을 돌면서 dfs를 통해 탐색한다. dfs는 boolean 타입을 리턴하도록 코드를 작성하였다. 만약 해당 좌표가 dfs를 통해서 true가 나온다면 카운트를 1 증가시킨다.
• dfs는 우선 입력되는 좌표가 배열의 범위 밖이라면 false를 리턴한다.
• 만약 해당 좌표의 값이 1이면, 해당 좌표는 이미 검증된 좌표이기 때문에 0으로 바꿔주고, 상, 하, 좌, 우 를 재귀를 통해 호출하며 탐색하고 탐색을 마치면 true를 리턴한다.
• 만약 해당 좌표의 값이 0이면 if문을 타지 않고 false를 리턴하게 된다.
• 위 과정을 반복하여 스트링 빌더에 count의 값을 추가시켜준다.