본문 바로가기

PS

[BOJ] 2583번: 영역 구하기

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

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

분류 : 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)이라는 점이 걸렸지만 상관없이 그냥 구해도 답은 나오는 듯하다.

 

'PS' 카테고리의 다른 글

[BOJ] 1987번 : 알파벳  (0) 2017.06.10
[BOJ] 2468번: 안전 영역  (0) 2017.06.09
[BOJ] 11049번: 행렬 곱셈 순서  (0) 2017.06.08
[BOJ] 2667번: 단지번호붙이기(DFS)  (0) 2017.06.07
[BOJ] 1012번 : 유기농 배추(DFS)  (0) 2017.06.07