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

문제링크:

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개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

 

출력:

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

 

 

문제 이해:

이 문제를 이해하기 위해서 예시를 확인하면서 이해하는 것이 가장 쉽다.

예제 입력 1을 통해 출력 결과가 3 \n 1 7 13이 되는지 알아보자

맨 위 왼쪽 귀퉁이에 있는 작은 공간은 단 1칸만 존재한다. 따라서 DFS로 탐색하면 한 번만 탐색하고 종료된다. 즉, 넓이 1이다.

다음은 오른쪽 위부터 아래로 이어진 길다란 공간이다. 이 공간은 총 7칸이 연결되어 있으며, DFS가 이 칸들을 차례대로 탐색하게 된다. 결과적으로 DFS 탐색 횟수 = 넓이 = 7이 된다.

마지막으로 가장 큰 공간은 왼쪽 아래에 위치한 영역으로, 사각형 2개가 이 영역을 감싸고 있어 넓게 연결되어 있다. DFS가 이 공간을 탐색하면 총 13칸을 방문하게 되며, 넓이는 13이 된다.

이처럼 DFS를 통해 연결된 0의 영역을 탐색할 때마다, 탐색한 칸의 수가 곧 그 영역의 넓이가 된다. 그리고 모든 영역의 넓이를 벡터에 저장한 후, 정렬하여 출력하면 문제에서 요구한 결과와 동일하게 나온다.

즉,

• 총 3개의 영역이 있으며,
• 각 영역의 넓이는 1, 7, 13,
• 이를 오름차순 정렬하면 출력은 3 \n 1 7 13이 되는 것이다.

이를 코드로 구현하기 위해서 먼저 0.0이 왼쪽 하단에 있다는 것에 불편함을 느낄 수 있다. 따라서 이를 y축으로 대칭시켜 진행하면 편할 것이다. 즉 x1을 입력받을 때 y1에, y1을 입력받을 때 x1에 저장하면 편하다. 이는 다음과 같은 그림이다.

 

 

구현 방식:

먼저 도화지의 크기(N행 M열)와 색칠할 직사각형의 개수(K)를 입력받는다.

 

이후 K개의 직사각형 좌표를 입력받아 해당 영역을 1로 표시한다. 이는 색칠된 부분을 의미한다.

 

그 다음, 도화지 전체를 한 칸씩 순회하면서 아직 방문하지 않았고, 색칠되지 않은 칸(0)을 발견하면 거기서부터 BFS 탐색을 시작한다. BFS는 인접한 상하좌우 방향으로 퍼져나가며 같은 영역을 확장해 나간다.

 

탐색이 끝날 때마다 넓이를 계산하여 결과 벡터에 저장한다.

 

모든 탐색이 끝나면 벡터를 오름차순 정렬하고, 영역의 개수와 각 영역의 넓이를 출력한다.

 

DFS 방식도 구현되어 있지만, 현재는 BFS로 동작하도록 되어 있다.

이를 코드로 구현하면 다음과 같다.

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[][] matrix;
    static boolean[][] visited;
    static int result = 0;

    //dfs 탐색
    public static void dfs(int x, int y) {
        visited[x][y] = true;
        result++;

        // 상
        if (x > 0 && matrix[x - 1][y] == 0 && !visited[x - 1][y]) {
            dfs(x - 1, y);
        }

        // 하
        if (x + 1 < matrix.length && matrix[x + 1][y] == 0 && !visited[x + 1][y]) {
            dfs(x + 1, y);
        }

        // 좌
        if (y > 0 && matrix[x][y - 1] == 0 && !visited[x][y - 1]) {
            dfs(x, y - 1);
        }

        // 우
        if (y + 1 < matrix[0].length && matrix[x][y + 1] == 0 && !visited[x][y + 1]) {
            dfs(x, y + 1);
        }
    }


    //bfs탐색
    public static void bfs(int x, int y) {
        visited[x][y] = true;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x1 = cur[0];
            int y1 = cur[1];
            result++;

            // 상
            if (x1 > 0 && matrix[x1 - 1][y1] == 0 && !visited[x1 - 1][y1]) {
                q.offer(new int[]{x1 - 1, y1});
                visited[x1 - 1][y1] = true;
            }

            // 하
            if (x1 + 1 < matrix.length && matrix[x1 + 1][y1] == 0 && !visited[x1 + 1][y1]) {
                q.offer(new int[]{x1 + 1, y1});
                visited[x1 + 1][y1] = true;
            }

            // 좌
            if (y1 > 0 && matrix[x1][y1 - 1] == 0 && !visited[x1][y1 - 1]) {
                q.offer(new int[]{x1, y1 - 1});
                visited[x1][y1 - 1] = true;
            }

            // 우
            if (y1 + 1 < matrix[0].length && matrix[x1][y1 + 1] == 0 && !visited[x1][y1 + 1]) {
                q.offer(new int[]{x1, y1 + 1});
                visited[x1][y1 + 1] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {

        int N, M, K;
        Vector<Integer> v = new Vector<>(); // 결과 담을 벡터

        // N, M, K 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

        // K개의 직사각형 영역 색칠
        // 대칭해서 보기 쉽게 0.0이 가장 위로 가게 변환
        for (int i = 0; i < K; i++) {
            int x1, x2, y1, y2;
            st = new StringTokenizer(br.readLine(), " ");
            y1 = Integer.parseInt(st.nextToken());
            x1 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());

            for (int j = x1; j < x2; j++) {
                for (int k = y1; k < y2; k++) {
                    matrix[j][k] = 1; //영역 색칠
                }
            }
        }

        // DFS 탐색하여 영역 크기 측정
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && matrix[i][j] == 0) {
                    result = 0;
//                    dfs(i, j);
                    bfs(i, j);
                    v.add(result);
                }
            }
        }

        // 결과 정렬 및 출력
        Collections.sort(v);
        System.out.println(v.size());
        for (int i = 0; i < v.size(); i++) {
            System.out.print(v.get(i));
            if (i != v.size() - 1) System.out.print(" ");
        }
    }
}

 

 

 

BFS, DFS 모두 정답이 된 것을 확인할 수 있다.

 

마무리하며:

이 문제는 단순한 구현 문제처럼 보일 수 있지만, 좌표를 정확히 처리하고 탐색 범위를 올바르게 설정하는 것이 중요하다. DFS나 BFS를 통해 연결된 영역을 찾아내는 기본 원리를 익히는 데에 매우 좋은 예제다. 특히, 문제를 직접 그림으로 확인하면서 영역이 어떻게 나뉘는지 시각적으로 이해하면, 탐색 알고리즘의 흐름을 훨씬 더 쉽게 파악할 수 있다.

 

탐색과 좌표 처리에 익숙해지는 것이 목표라면, 이 문제를 꼭 한번 스스로 구현해보며 익혀두는 것이 좋다.

 

감사합니다.