[백준] 2583번 : 영역 구하기

2583번: 영역 구하기

# 문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

# 입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

# 출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

# 예제 입력

5 7 3

0 2 4 4

1 1 2 5

4 0 6 2

# 예제 출력

3

1 7 13

---

[BFS]

입력으로 주어지는 왼쪽 아래 꼭지점(y1, x1)과 오른쪽 위 꼭지점(y2, x2)를 적절히 for문을 돌며 map[][] 2차원 배열에 1로 할당해준다.

 

완성된 map[][]을 가지고 BFS를 돌며 영역의 개수(cnt)와 각 영역의 면적(area)를 증가시키며 구하고, 영역의 면적은 오름차순 정렬 후 출력한다.

# Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int y, int x){
            this.y=y; this.x=x;
        }
    }
    static int n,m,k, cnt = 0;
    static int[][] map = new int[101][101];
    static Queue<Point> Q = new LinkedList<>();
    static boolean[][] visit = new boolean[101][101];
    static List<Integer> list = new ArrayList<>();
    static int[] Y = {1, -1, 0, 0};
    static int[] X = {0, 0, 1, -1};

    static void BFS(){

        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++){
                int area = 0;
                if(!visit[i][j] && map[i][j] == 0){
                    cnt++; //영역 개수 증가
                    area++; //면적 증가
                    visit[i][j] = true;
                    Q.add(new Point(i, j));
                }
                while(!Q.isEmpty()){
                    Point p = Q.poll();
                    int y = p.y;
                    int x = p.x;

                    for(int a=0; a<4; a++) {
                        int ny = y + Y[a];
                        int nx = x + X[a];

                        if ((ny >= 0 && ny < m) && (nx >= 0 && nx < n) && !visit[ny][nx] && map[ny][nx] == 0) {
                            visit[ny][nx] = true;
                            area++;
                            Q.add(new Point(ny, nx));
                        }
                    }
                }
                if(area != 0)
                    list.add(area);
            }//.2for
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=0; i<k; i++){
            st = new StringTokenizer(br.readLine());

            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            for(int a=y1; a<y2; a++)
                for(int b=x1; b<x2; b++)
                    map[a][b] = 1;

        }
        BFS();
        Collections.sort(list); //정렬

        System.out.println(cnt);
        for(int a:list)
            System.out.print(a + " ");
    }
}