[ 백준 - Java ] 영역 구하기 ( 자바 )

( dfs / 영역 구하기 / 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개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

제한사항

메모리 제한 : 128 MB

입출력 예시

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

 

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

---

[코드]

import java.util.PriorityQueue;
import java.util.Scanner;

public class GetArea2583 {
    static int m;           // 세로 길이
    static int n;           // 가로 길이
    static int k;           // 네모의 개수
    static boolean[][] map; // 좌표정보를 담은 배열
    static int answer;      // 빈 영역을 카운트해줄 변수
    static PriorityQueue<Integer> pq = new PriorityQueue<>();   // 넓이 오름차순으로 출력해주기위해 사용한 우선순위큐
    // x, y 다음 좌표 변경시 증감 값
    static final int[] dx = {0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args){
        // === 입력 ===
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();   // 세로 크기 입력
        n = sc.nextInt();   // 가로 크기 입력
        k = sc.nextInt();   // 사각형 개수 입력
        // 가로 세로 크기로 초기화
        map = new boolean[m][n];
        // 사각형 부분 방문처리
        for(int i = 0; i < k; i++){
            // 왼쪽 아래 좌표와 오른쪽 위 좌표 입력
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            // 해당 사각형 범위 방문처리
            for(int y = y1; y < y2; y++){
                for(int x = x1; x < x2; x++) map[y][x] = true;
            }
        }

        sc.close();

        // === 풀이 ===
        int cnt = 0;    // 영역 카운트변수 초기화
        answer = 0;     // 영역의 넓이 카운트변수 초기화
        // 깊이 우선 탐색
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // 방문하지 않은 구역일 경우 깊이 우선 탐색
                if(!map[i][j]){
                    dfs(j, i);          // 깊이 우선 탐색
                    cnt++;              // 영역카운트 증가
                    pq.offer(answer);   // 영역 넓이 우선순위큐에 추가
                    answer = 0;         // 다음 영역 넓이를 카운트하기 위해 초기화
                }
            }
        }

        // === 출력 ===
        // 영역 개수 출력
        System.out.println(cnt);
        // 영역 넓이 오름차순으로 출력
        while(!pq.isEmpty()) System.out.print(pq.poll() + " ");
    }

    // 깊이 우선 탐색
    public static void dfs(int x, int y){
        if(map[y][x]) return;   // 이미 방문했거나 색칙된 부분일 경우 깊이 우선 탐색 중단

        map[y][x] = true;   // 현재 위치 방문처리
        answer++;           // 현재 위치가 포함된 넓이 증가
        // 4방향으로 깊이 우선 탐색 시도
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];     // 다음 x좌표
            int ny = y + dy[i];     // 다음 y좌표
            // map구역을 넘지 않으면서 다음 위치가 방문하지 않았거나 색칠된 영역이 아닌 경우
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && !map[ny][nx]){
                dfs(nx, ny);        // 깊이 우선 탐색
            }
        }
    }
}

문제 링크

2583번: 영역 구하기

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄