1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package backjun;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class backjun_1012_유기농배추 {
 
    static int[][] map;
    static int[] dx= {-1,1,0,0};
    static int[] dy= {0,0,-1,1};
    static int[][] check;
    static int M;
    static int N;
    
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int total = Integer.parseInt(br.readLine());
        while(total-->0) {
        StringTokenizer st = new StringTokenizer(br.readLine());
         M = Integer.parseInt(st.nextToken());
         N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //가로, 세로, 위치 개수
        map = new int[M][N];
        check = new int[M][N];
        for(int i=0; i<K; i++)
        {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = 1;
        }
        int ans = 0;
        
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 && check[i][j] ==0) {
                    check[i][j] = 1;
                    ans +=1;
                    dfs(i,j);
                    
                }
            }
        }
        System.out.println(ans);
        }
        
    }
    static void dfs(int x, int y) {
        
        for(int i=0; i<4; i++) {
            int ddx = x + dx[i];
            int ddy = y + dy[i];
            if(ddx<0 || ddx>=|| ddy<0 || ddy>=N) {
                continue;
            
            }
            if(map[ddx][ddy] ==1 && check[ddx][ddy] == 0) {
                check[ddx][ddy] = 1;
                dfs(ddx,ddy);
            }
        }
    }
 
}
 
cs

1을 묶음 단위로 DFS 구현하면 해결할 수 있습니다.

기본적으로 완전탐색 문제에 해당됩니다.