[BOJ] 1012번 : 유기농 배추(DFS)

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

1012번: 유기농 배추

 

알고리즘 분류 : DFS, BFS

 

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int[][] farm = new int[51][51];
    static boolean[][] visited = new boolean[51][51];
    static int M, N, K;

    public static void main(String[] args) {

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {

            M = sc.nextInt();
            N = sc.nextInt();
            K = sc.nextInt();

            for (int warm = 0; warm < K; warm++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                farm[y][x] = 1;
            }
            int cnt = 0;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < M; c++) {
                    if (farm[r][c] != 0 && !visited[r][c]) {
                        cnt++;
                        DFS(r, c);
                    }
                }
            }
            out.println(cnt);
            for (int i = 0; i < 51; i++) {
                Arrays.fill(farm[i], 0);
                Arrays.fill(visited[i], false);
            }

        }
        out.close();

    }

    private static void DFS(int r, int c) {

        if (r < 0 || r > N || c < 0 || c > M || visited[r][c] || farm[r][c] == 0)
            return;
        
        visited[r][c] = true;
        
        DFS(r - 1, c);
        DFS(r + 1, c);
        DFS(r, c - 1);
        DFS(r, c + 1);
    }
}

예전에는 BFS로 모든 문제를 해결해 나가려고 했는데 DFS로 한번 해결해보았다.

 

문제에서 주어지는 M (가로길이), N(세로 길이)와 배추의 위치가 (x, y) 좌표가 아닌 (y, x) 좌표인 것을 조심하면 쉽게 통과할 수 있다.