백준 2583: 영역 구하기

풀이

• 2차원 배열 'map'에 직사각형이 있는 부분을 true로 설정
• 0,0 부터 BFS실행 (직사각형이 없는 경우 & 방문하지 않은 경우만)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.util.Collections.sort;

public class Problem2583 {
    static int height, weight, recNum;
    static int[] dirX = new int[]{0,0,1,-1};
    static int[] dirY = new int[]{1,-1,0,0};
    static boolean[][] map, visited;
    static int secNum = 0;
    static ArrayList<Integer> secSize = new ArrayList<>();

    public static int bfs(int[] startNode){
        int sizeTemp = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(startNode);
        visited[startNode[0]][startNode[1]] = true;

        while (!queue.isEmpty()){
            int[] curNode = queue.poll();
            for (int d = 0; d < 4; d++) {
                int newX = curNode[1] + dirX[d];
                int newY = curNode[0] + dirY[d];

                if (newX < 0 || newX >= weight || newY < 0 || newY >= height) continue;

                //4방향에 값이 존재 & 미방문
                if (!map[newY][newX]  && !visited[newY][newX]) {
                    queue.add(new int[]{newY, newX});
                    visited[newY][newX] = true;
                    sizeTemp++;
                }
            }
        }

        return sizeTemp;
    }



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

        height = Integer.parseInt(st.nextToken());
        weight = Integer.parseInt(st.nextToken());
        recNum = Integer.parseInt(st.nextToken());

        map = new boolean[height][weight];
        visited = new boolean[height][weight];

        for(int i = 0; i < recNum; i++){
            String recStr = br.readLine();
            StringTokenizer recSt = new StringTokenizer(recStr, " ");
            int[] firTemp = new int[]{Integer.parseInt(recSt.nextToken()), Integer.parseInt(recSt.nextToken())};
            int[] secTemp = new int[]{Integer.parseInt(recSt.nextToken()), Integer.parseInt(recSt.nextToken())};
            for(int y = firTemp[1]; y < secTemp[1]; y++){
                for(int x = firTemp[0]; x < secTemp[0]; x++){
                    map[y][x] = true;
                }
            }
        }

        for(int y = 0; y < height; y++){
            for(int x = 0; x < weight; x++){
                if(!map[y][x] && !visited[y][x]){
                    int size = bfs(new int[]{y, x});
                    secSize.add(size);
                    secNum++;
                }
            }
        }

        sort(secSize);

        System.out.println(secNum);

        String ansStr = "";
        for(int i : secSize){
            ansStr += i + " ";
        }
        //공백 제거
        ansStr = ansStr.trim();
        System.out.println(ansStr);
    }
}