[알고리즘 PS] 백준 2583번 영역 구하기 자바 문제풀이

문제

해당 포스팅은 백준의 2583번 영역 구하기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

2583번: 영역 구하기

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 BFS 나 DFS 모두 풀 수 있는 문제이다.

 

여기서 이 문제를 해결하기 위한 중요한 팁은 모눈 종이를 어떻게 바라볼 것이냐? 였던것 같다.

 

만약 배열로 생각을 한다면 모눈 종이를 2가지 관점? 으로 바라볼 수 있다.

 

1. 각각 꼭지점을 좌표로 볼 것인가?
2. 하나의 사각형을 좌표로 볼 것인가?

 

이번 문제는 하나의 좌표는 넓이가 1인 정사각형 으로 취급하므로 2번 쨰 관점으로 보는 것이 매우 편할 것이다.

 

정답 코드

 

public class Main {

    private static int m;
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] mnk = br.readLine().split(" ");

        m = Integer.parseInt(mnk[0]); // y
        n = Integer.parseInt(mnk[1]); // x
        int k = Integer.parseInt(mnk[2]); // 개수

        boolean[][] arr = new boolean[m][n];

        for (int i = 0; i < k; i++) {
            String[] s = br.readLine().split(" ");
            int fromX = Integer.parseInt(s[0]);
            int fromY = Integer.parseInt(s[1]);

            int toX = Integer.parseInt(s[2]);
            int toY = Integer.parseInt(s[3]);

            mark(arr, fromX, fromY, toX, toY); // 색칠
        }

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if(!arr[i][j]) {
                    list.add(getConnectedComponent(arr, j, i));
                }
            }
        }
        Collections.sort(list);

        bw.write(list.size() + "\n");

        for(int value : list) {
            bw.write(value + " ");
        }

        bw.flush();
        bw.close();
    }

    private static void mark(boolean[][] arr, int fromX, int fromY, int toX, int toY) {
        for (int i = fromY; i < toY; i++) {
            for (int j = fromX; j < toX; j++) {
                arr[i][j] = true;
            }
        }
    }

    private static int getConnectedComponent(boolean[][] arr, int x, int y) {

        int[] xPos = {1, -1, 0, 0};
        int[] yPos = {0, 0, 1, -1};

        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(x, y));
        arr[y][x] = true;

        int count = 1;

        while(!queue.isEmpty()) {
            Position front = queue.remove();

            for (int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];

                if(0 <= xx && xx < n && 0 <= yy && yy < m) {
                    if(!arr[yy][xx]) {
                        arr[yy][xx] = true;
                        queue.add(new Position(xx, yy));
                        count++;
                    }
                }
            }
        }

        return count;
    }

    private static class Position {
        int x;
        int y;

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

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.