[JAVA] 백준 2593 : 영역 구하기

문제

눈금 간격이 MxN인 크기의 모눈종이 위에 눈금에 맞춰 K개의 직사각형을 그릴 때, K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지 구하고, 각각 영역의 크기를 오름차순으로 출력하는 문제.

※ 예제 : (0,2) (4,4) , (1,1) (2,5) , (4,0) (6,2) 로 입력을 받았음.

접근방법

1. 주어진 모눈종이는 보통 사용하는 이차원 배열과는 조금 다르게 생겼다. 이차원배열로 구현하기 위해 조금 바꾸어준다.

   1) 왼쪽 위가 (0,0)이 되도록 모눈종이를 뒤집어도, 결과 영역은 달라지는게 없으므로, 원래 배열과 같이 (0,0)을 가장 위로 생각하고 입력을 받는다.

   2) 이차원배열과 달리 모눈종이의 '점'을 입력으로 받기 때문에, 이를 배열의 '칸'으로 바꿔주어야 한다.

   • 각 점이 아니라, 각 칸을 기준으로 좌표를 계산하면 처음 입력했던 (0,2)는 (2,0)에 들어가며, (4,4)는 (3,3)에 들어간다. 즉, 마지막 점을 배열의 칸으로 변경하면 해당 점의 왼쪽 위 좌표와 동일하므로, 행, 열에서 1씩 빼준 값을 넣어주면 된다.

2. 영역의 개수를 구하는 부분은 BFS를 이용한다.

3. 영역별 크기를 구하기 위해서는 BFS 함수를 실행할 때 size를 체크해준다. 즉, 큐에 원소를 넣을 때 마다 size를 증가시켜준다.

4. 영역별 크기를 오름차순으로 출력하기 위해서 Collection을 이용한다. ArrayList를 정렬하는 코드 : Collections.sort(sizeList);

소스코드

public class Main {
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x = x; this.y = y;}
    }
​
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int result = 0;
    static int N, M, K;
    static boolean[][] visited;
    static int[][] map;
    static Queue<Pos> queue;
    static ArrayList<Integer> sizeList;
​
    static void BFS(){
        int size = 1;
        while(!queue.isEmpty()){
            Pos cur_pos = queue.poll();
​
            for(int i=0; i<4; i++){
                Pos next_pos = new Pos(cur_pos.x + dx[i], cur_pos.y + dy[i]);
                if(map[next_pos.x][next_pos.y] != 1 && !visited[next_pos.x][next_pos.y]){
                    visited[next_pos.x][next_pos.y] = true;
                    queue.offer(next_pos);
                    ++size;
                }
            }
        }
        sizeList.add(size);
    }
​
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
        String input[] = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        K = Integer.parseInt(input[2]);
​
        visited = new boolean[N+2][M+2];
        map = new int[N+2][M+2];
        
        // 벽 설정(배열범위 초과 방지)
        for(int i=0; i<=N+1; i++)
            for(int j=0; j<=M+1; j++)
                if(i==0 || i==N+1 || j==0 || j==M+1)
                    map[i][j] = 1;
​
        // 색칠된 부분 1로 변경
        for (int i = 0; i < K; i++) {
            String[] pos = in.readLine().split(" ");
            int start_y = Integer.parseInt(pos[0]);
            int start_x = Integer.parseInt(pos[1]);
            int end_y = Integer.parseInt(pos[2])-1;
            int end_x = Integer.parseInt(pos[3])-1;
​
            for (int r = start_x; r <= end_x; r++)
                for (int c = start_y; c <= end_y; c++)
                    map[r][c] = 1;
        }
​
        // BFS
        sizeList = new ArrayList<>();
        queue = new LinkedList<>();
        for(int i=1; i<=N; i++)
            for(int j=1; j<=M; j++)
                if(map[i][j] == 0 && !visited[i][j]){
                    ++result;
                    visited[i][j] = true;
                    queue.offer(new Pos(i, j));
                    BFS();
                }
​
        // 각 영역별 크기 정렬
        Collections.sort(sizeList);
        System.out.println(result);
        for(int i=0; i<sizeList.size(); i++)
            System.out.print(sizeList.get(i) + " ");
​
    }
​
}