알고리즘94 :: BOJ_1012_유기농배추

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>=M || ddy<0 || ddy>=N) {
                continue;
            
            }
            if(map[ddx][ddy] ==1 && check[ddx][ddy] == 0) {
                check[ddx][ddy] = 1;
                dfs(ddx,ddy);
            }
        }
    }
 
}
 

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

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