[백준 2583] 영역 구하기 (Java)

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

2583번: 영역 구하기

접근 방법

탐색을 위해 입력받은 모눈종이 정보를 2차원 배열로 변환했다.

직사각형이 들어간 칸은 1, 그렇지 않은 칸은 0으로 표기했다.

 

배열과 다르게 모눈종이는 왼쪽 아래에서 오른쪽 위로 숫자가 커지는 차이가 있었다.

배열을 입력값 대로 무작정 값을 받게되면 문제의 그림과는 상하 대칭이 되지만 결과값에는 크게 지장을 주지 않았다.

 

bfs든 dfs든(나는 bfs 사용) 값이 0이고 방문한 적이 없는 곳을 방문하고 방문할 때마다 count++를 함으로써 면적을 구했다.

구한 결과를 리스트에 담아두고 출력할 때 영역의 개수는 리스트의 사이즈를 출력하고 영역의 넓이는 오름차순으로 정렬한 뒤 출력했다.

 

소스 코드

import java.util.*;

public class Main {
    private static int M;
    private static int N;
    private static int K;
    private static int[][] map;
    private static boolean[][] visited;
    private static List<Integer> results = new ArrayList<>();
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        M = scanner.nextInt();
        N = scanner.nextInt();
        K = scanner.nextInt();

        map = new int[M][N];
        visited = new boolean[M][N];

        for (int i = 0; i < K; i++) {
            int startY = scanner.nextInt();
            int startX = scanner.nextInt();
            int endY = scanner.nextInt();
            int endX = scanner.nextInt();

            for (int j = startX; j < endX; j++) {
                for (int k = startY; k < endY; k++) {
                    map[j][k] = 1;
                }
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0 && !visited[i][j]) {
                    bfs(i, j);
                }
            }
        }

        Collections.sort(results);
        StringBuilder result = new StringBuilder();

        for (int number : results) {
            result.append(number).append(" ");
        }

        System.out.println(results.size());
        System.out.println(result.toString().trim());
    }

    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();

        visited[x][y] = true;
        queue.add(new Point(x, y, 0));

        int count = 0;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            count++;

            for (int i = 0; i < 4; i++) {
                int newX = point.x + dx[i];
                int newY = point.y + dy[i];

                if (isInArea(newX, newY) && map[newX][newY] == 0 && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    queue.add(new Point(newX, newY, point.depth + 1));
                }
            }
        }

        results.add(count);
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && x < M && y >= 0 && y < N;
    }


    static class Point {
        private int x;
        private int y;
        private int depth;

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