[BOJ] 백준 2583 영역 구하기

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

 Input 

5 7 3

0 2 4 4

1 1 2 5

4 0 6 2

 

 Output 

3

1 7 13

직사각형의 정보는 아래와 같습니다. 　

문제에서 주어진 인덱스를 아래와 같이 해석해도 무방.

 

3개의 분리된 영역과 그 넓이는 아래와 같습니다.

① 모눈 종이를 순회하며 직사각형으로 안 덮여진 지점을 찾습니다.

② BFS를 통해 분리된 영역을 구분합니다.

③ 분리된 영역의 개수와 각각의 넓이를 구합니다.

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
 
public class Main {
     
    static int[][] arr;
    static List<Integer> areaList;
    static int[] dx, dy;
    static int N, M;
    static Queue<Node> queue;
     
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
         
        M = Integer.parseInt(sc.next());
        N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
         
        // x,y좌표를 바꿔서 표현
        arr = new int[N][M];
         
        while(K-- > 0) {
            int x1 = Integer.parseInt(sc.next());
            int y1 = Integer.parseInt(sc.next());
            int x2 = Integer.parseInt(sc.next());
            int y2 = Integer.parseInt(sc.next());
             
            for(int i=x1; i<x2; i++) {
                for(int j=y1; j<y2; j++) {
                    arr[i][j] = 1;
                }
            }
        }
         
        // 영역의 개수
        int areaCnt = 0;
         
        // 동서남북(이동 범위)
        dx = new int[] {1, -1, 0, 0};
        dy = new int[] {0, 0, -1, 1};
         
        // BFS를 위한 자료구조 '큐'
        queue = new LinkedList<>();
        areaList = new ArrayList<>();
         
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                // 탐색대상에 해당된다면 BFS 탐색(방문하지 않은 곳)
                if(arr[i][j] == 0) {
 
 
                    // 방문 표시
                    arr[i][j] = 1;
                    queue.add(new Node(i, j));
 
 
                    BFS();
                     
                    // 영역의 개수 올리기
                    areaCnt++;
                }
            }
        }
         
        // 영역의 개수 출력
        System.out.println(areaCnt);
         
        // 영역의 너비를 오름차순 정렬 후 출력
        Collections.sort(areaList);
        while(!areaList.isEmpty()) System.out.print(areaList.remove(0) + " ");
         
         
    }
 
 
    private static void BFS() {
        // 해당 영역의 시작점 영역의 넓이를 '1'로 시작
        int area = 1;
        // 탐색 가능한 모든 지점을 탐색할 때까지
        while(!queue.isEmpty()) {
            Node curNode = queue.poll();
             
            for(int i=0; i<4; i++) {
                int next_x = curNode.x + dx[i];
                int next_y = curNode.y + dy[i];
                 
                // 배열의 범위내에서
                if(next_x < 0 || next_y < 0) continue;
                if(next_x >= N || next_y >= M) continue;
                 
                // 방문한 곳이거나 분리된 지점이라 탐색이 불가능한다면 continue
                if(arr[next_x][next_y] == 1) continue;
                // 방문(탐색) 표시
                arr[next_x][next_y] = 1;
                // 영역의 넓이 값 올리기
                area++;
                // 해당 지점과 연결된 지점을 계속해서 탐색하기 위해 queue에 삽입
                queue.add(new Node(next_x, next_y));
                 
            }
        }
         
        // BFS 탐색이 종료한 뒤 구해진 너비를 넣어둔다.
        areaList.add(area);
         
    }
}
 
 
class Node{
    int x,y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}