[백준 / 실버1] 2583 영역 구하기 (Java)

문제 보기

사용한 것

• 빈 영역의 개수, 빈 영역 하나당 크기를 구하기 위한 BFS

풀이 방법

• 2차원 visited 배열을 만들어 입력 받은 사각형에 포함되는 영역을 true로 만든다.
• 입력이 끝나면 visited에 대해 2중 for문을 돌며 빈 영역(false)을 발견하면 numOfEmptyAreas을 증가시키고 BFS 돈다.
• BFS 돌면서 방문한 좌표들의 visited를 true로 바꾸고 sizeOfEmptyArea를 증가시킨다.
• BFS 끝나면 sizesOfEmptyAreas에 빈 영역의 크기인 sizeOfEmptyArea를 넣는다.
• 빈 영역의 크기들을 오름차순해서 출력해야하므로 sizesOfEmptyAreas을 sort()한다.

코드

public class Main {

    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] splitLine = br.readLine().split(" ");
        int m = Integer.parseInt(splitLine[0]);
        int n = Integer.parseInt(splitLine[1]);
        int k = Integer.parseInt(splitLine[2]);
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < k; i++) {
            splitLine = br.readLine().split(" ");
            int x1 = Integer.parseInt(splitLine[0]);
            int y1 = Integer.parseInt(splitLine[1]);
            int x2 = Integer.parseInt(splitLine[2]);
            int y2 = Integer.parseInt(splitLine[3]);

            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    visited[x][y] = true;
                }
            }
        }

        int numOfEmptyAreas = 0;
        List<Integer> sizesOfEmptyAreas = new ArrayList<>();

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (visited[x][y]) {
                    continue;
                }

                numOfEmptyAreas++;
                Queue<int[]> q = new LinkedList<>();
                q.offer(new int[]{x, y});
                visited[x][y] = true;
                int sizeOfEmptyArea = 0;

                while (!q.isEmpty()) {
                    sizeOfEmptyArea++;
                    int[] cp = q.poll();
                    int cx = cp[0];
                    int cy = cp[1];

                    for (int i = 0; i < 4; i++) {
                        int nx = cx + dx[i];
                        int ny = cy + dy[i];

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) {
                            continue;
                        }

                        q.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }

                sizesOfEmptyAreas.add(sizeOfEmptyArea);
            }
        }

        Collections.sort(sizesOfEmptyAreas);
        StringBuilder sb = new StringBuilder();
        for (int sizeOfEmptyArea : sizesOfEmptyAreas) {
            sb.append(sizeOfEmptyArea).append(" ");
        }

        System.out.println(numOfEmptyAreas);
        System.out.println(sb);
    }
}