[백준 1012] 유기농 배추

 

DFS, BFS 를 이용하여 푸는 기본 문제이다.

 

 

풀이

1. n*m 의 배열을 만들어 0 또는 1을 대입한다.

2. 배열의 값이 1일때 상하좌우로 1이 있는지 탐색한다.

3. 탐색한 인덱스에 0을 대입한다.

4. 가로 n, 세로 m 은 배열에서 a[m][n] 이므로 실수하지 말자.

 

 

public class Main {
    
    static int mx[] = {-1, 0, 1, 0};
    static int my[] = {0, 1, 0, -1};
    static int a[][];
    static int m;
    static int n;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        
        while(t-->0) {
            m = sc.nextInt();
            n = sc.nextInt();
            int k = sc.nextInt();
            
            a = new int[n][m];
            
            for(int i=0; i<k; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                a[y][x] = 1;
            }
            
            int cnt = 0;
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(a[i][j] != 0) {
                        dfs(i, j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
        sc.close();
    }
    
    public static void dfs(int x, int y) {
        if(a[x][y] == 0)
            return;
        
        a[x][y] = 0;
        
        for(int i=0; i<4; i++) {
            int nx = x + mx[i];
            int ny = y + my[i];
            
            if(0 <= nx && nx < n && 0 <= ny && ny < m)
                dfs(nx, ny);
        }
    }
}