백준 2583 - 영역 구하기

문제

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

리뷰

전형적인 BFS를 이용하여 풀이하는 문제였다. 문제에서 주어진 좌표 공간이 코드에서의
좌표와 반전되어 있어 로직에서 다르게 표현해야 하나 고민할 수 있지만, 그저 상하로
반전되어 있는 형태이기 때문에 그대로 구현하였다. 로직의 전개는 아래와 같다.

• 직사각형 범위에 속하는 공간을 visited 배열에서 모두 방문 처리해준다.
• bfs 를 돌리며 직사각형의 크기를 구하고 results에 추가해준다.
  bfs가 호출되는 횟수가 직사각형의 개수이다.
• results 를 오름차순으로 출력하기 위해 정렬한다.

이 로직에서 가장 큰 시간복잡도 $O(KNM)$ 이므로 최대 $100^3$ 연산을 수행하기에
주어진 1초의 제한 조건을 무난히 통과한다.

코드

import java.io.*;
import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int N, M;
    static boolean[][] visited;
    static int[] px = {-1, 1, 0, 0};
    static int[] py = {0, 0, -1, 1};

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

        visited = new boolean[M][N];

        int K = parseInt(st.nextToken());

        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            int startX = parseInt(st.nextToken());
            int startY = parseInt(st.nextToken());
            int endX = parseInt(st.nextToken());
            int endY = parseInt(st.nextToken());

            paintRectangle(new Point(startX, startY), new Point(endX, endY));
        }

        List<Integer> results = new ArrayList<>();
        int count=0;

        for (int y = 0; y < M; y++)
            for (int x = 0; x < N; x++) {
                if (!visited[y][x]) {
                    results.add(bfs(new Point(x, y)));
                    count++;
                }
            }

        System.out.println(count);
        Collections.sort(results);
        results.forEach(num -> System.out.print(num + " "));
        br.close();
    }

    static int bfs(Point start) {
        Queue<Point> queue = new ArrayDeque<>();
        visited[start.y][start.x] = true;
        queue.offer(start);

        int area = 1;

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            for (int i = 0; i < px.length; i++) {
                int nextX = current.x + px[i];
                int nextY = current.y + py[i];

                if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) {
                    if (!visited[nextY][nextX]) {
                        visited[nextY][nextX] = true;
                        queue.offer(new Point(nextX, nextY));
                        area++;
                    }
                }
            }
        }

        return area;
    }


    static void paintRectangle(Point start, Point end) {
        for (int y = start.y; y < end.y; y++)
            for (int x = start.x; x < end.x; x++) {
                visited[y][x] = true;
            }
    }

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

결과