[JAVA 알고리즘]BAEKJOON 2583번 영역 구하기

영역 구하기

---

문제 설명

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

제한사항

• 없음

입출력 예

input	return
5 7 3 0 2 4 4 1 1 2 5 4 0 6 2	3 1 7 13

---

문제 분석

첫줄의 입력 값을 통해 배열의 크기와 반복 횟수를 이용할 수 있다.
좌표값 꼭짓점을 인덱스로 생각하면 위치를 파악하기 편하다. (단, 모양이 예시 형태의 대칭으로 나온다.)
대칭 형태라도 모양을 보는 게 아닌 크기를 보기 때문에 상관없다.
동일한 위치를 중복해서 표시를 해도 한 번 사용한 것과 같기 때문에 중복 위치는 표시를 안 하고 넘어가도 된다.
입력을 이용해서 색칠하는 로직과 색칠 안된 부분을 헤아리는 로직 2개가 필요하다.
색칠하는 부분은 이중 for문으로 색칠 안된 부분은 DFS, BFS를 사용하면 될 것 같다.

손으로 풀기

1. 첫 줄 입력값 M, N을 이용해 위치를 확인할 이차배열을 만들고 K만큼 반복문을 실행한다.
2. 반복문에서 입력값들을 받아 좌표값 범위 만큼을 반복하여 좌표 위치들을 사용 여부를 표시한다.
3. 횟수를 헤아릴 변수와 크기를 저장할 리스트를 만든다.
4. 이중 for문을 이용해 (0,0) 좌표부터 사용하지 않은 좌표를 찾는다.
5. 사용하지 않는 좌표의 경우, 횟 수를 헤아리고 해당 좌표를 사용 표시를 하고 DFS방식이나 BFS 방식을 사용해 크기를 리스트에 넣는다.
6. DFS 방식
   1. 상하좌우로 반복을 하면서 배열 범위안에서 사용하지 않았을 경우, 사용 표시를 하고 해당 좌표로 함수를 반복한다.
   2. 재귀함수이기 때문에 시작할 때 면적 값을 0으로 초기화하고 함수가 끝날 때 1 증가시키고 리턴을 시켜 누적값을 가져온다.
   3. 시작 면적이 안들어가기 때문에 종료 후 1을 더해서 리스트에 넣어준다.
7. BFS 방식
   1. 해당 좌표를 큐에 넣어 큐가 빌 때까지 반복한다.
   2. 큐에서 꺼낸 좌표로 상하좌우로 반복을 하면서 배열 범위 안에서 사용하지 않았을 경우, 사용 표시를 하고 해당 좌표를 큐에 넣는다.
   3. 면적을 1로 시작해 큐에 넣을 때마다 1씩 증가시켜주고 종료 후 리스트에 넣어준다.
8. 면적을 오름차순으로 정렬하고 횟수와 함께 출력한다.

나의 문제풀이

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

public class Main {
 
    static boolean[][] visited;
    static int M, N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        M = Integer.parseInt(stringTokenizer.nextToken());
        N = Integer.parseInt(stringTokenizer.nextToken());
        K = Integer.parseInt(stringTokenizer.nextToken());

        visited = new boolean[M][N];
        for (int i = 0; i < K; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int startY = Integer.parseInt(stringTokenizer.nextToken());
            int startX = Integer.parseInt(stringTokenizer.nextToken());
            int endY = Integer.parseInt(stringTokenizer.nextToken());
            int endX = Integer.parseInt(stringTokenizer.nextToken());
            for (int j = startX; j < endX; j++) {
                for (int k = startY; k < endY; k++) {
                    if (!visited[j][k]) {
                        visited[j][k] = true;
                    }
                }
            }
        }


        int cnt = 0;
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    cnt++;
                    visited[i][j] = true;
                    // DFS 방식
                    // 움직이는 횟수를 헤아리고 나오기 떄문에 현재 위치를 더해줘야한다.
                    answer.add(DFS(i, j) + 1);
                    // 재귀가 아니기 때문에 함수안에서 현재 위치를 더하고 올 수 있음.
//                    answer.add(BFS(i, j));

                }
            }
        }

        // 넓이를 오름차순으로 정렬
        answer.sort((o1, o2) -> o1 -o2);
        System.out.println(cnt);
        for (int i : answer) {
            System.out.print(i + " ");
        }
    }

    public static int DFS(int x, int y) {
        int cnt = 0;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N && !visited[nextX][nextY]) {
                visited[nextX][nextY] = true;

                // 다음으로 넘어 갈 때 0으로 가고 끝나고 1을 더할 수 있도록 증가를 뒤에 나둔다.
                cnt += DFS(nextX, nextY);
                cnt++;
            }
        }
        return cnt;
    }

    public static int BFS(int x, int y) {
        int cnt = 1;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            x = temp[0];
            y = temp[1];

            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];

                if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N && !visited[nextX][nextY]) {
                    visited[nextX][nextY] = true;

                    queue.offer(new int[]{nextX, nextY});
                    cnt++;
                }
            }
        }

        return cnt;
    }
}

이번 문제는 비교적 간단한 문제인지 DFS와 BFS방식에 따로 시간 차이가 나지 않았다.
간혹 문제에서 너비 우선 탐색이나 깊이 우선 탐색이 한쪽이 유리한 경우나 한쪽만 가능한 경우가 있는데, 그 부분도 구분을 할 수 있도록 반복해야겠다.

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

문제 출처 - https://www.acmicpc.net/problem/2583

2583번: 영역 구하기