[BOJ] 2583번: 영역 구하기

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

2583번: 영역 구하기

 

분류 : DFS, BFS

 

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

    public static void main(String[] args) {

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

        paper = new int[M][N];
        visited = new int[M][N];
        int result[] = new int[100*100+1];
        for (int tc = 0; tc < K; tc++) {
            int y1 = sc.nextInt();
            int x1 = sc.nextInt();
            int y2 = sc.nextInt();
            int x2 = sc.nextInt();

            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    paper[x][y] = 1;
                }
            }
        }
        color =0;
        for (int x = 0; x < M; x++) {
            for (int y = 0; y < N; y++) {
                if (paper[x][y] == 0 && visited[x][y] == 0) {
                    color++;
                    DFS(x,y);
                }
            }
        }
        for (int x = 0; x < M; x++) {
            for (int y = 0; y < N; y++) {
                if(visited[x][y]!=0) result[visited[x][y]]++;
                }
            }
        Arrays.sort(result);
        out.println(color);
        for(int idx =0; idx<result.length;idx++){
            if(result[idx]!=0){
                out.print(result[idx]+" ");
            }
        }
        out.close();
    }

    private static void DFS(int x, int y) {
        
        if(x<0 || x>=M || y<0 || y>=N || paper[x][y]==1 || visited[x][y]!=0) return;
        
        visited[x][y]=color;
        
        DFS(x-1,y);
        DFS(x+1,y);
        DFS(x,y-1);
        DFS(x,y+1);
    }
}

 

DFS를 통해 paper [x][y] ==0 인 지점을 탐색하며 color를 칠한 후에 result 배열을 정렬 후에 값 출력하면 완료.

문제에서는 왼쪽 아래가 (0,0)이라는 점이 걸렸지만 상관없이 그냥 구해도 답은 나오는 듯하다.