[BOJ/Java] 영역 구하기 (2583)

영역 구하기 (2583)

1. 문제 분석

문제 개요

• 주어진 평면의 크기와 색칠된 직사각형들의 좌표를 통해, 색칠되지 않은 영역의 개수와 각 영역의 크기를 구하는 문제이다.

입력 형식

• 첫 번째 줄에 평면의 세로 길이 N, 가로 길이 M, 색칠된 직사각형의 개수 K가 주어진다.
• 다음 K개의 줄에는 각 직사각형의 좌표가 주어진다. 좌표는 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 (x1, y1), (x2, y2) 형식으로 주어진다.

출력 형식

• 첫 번째 줄에는 색칠되지 않은 영역의 개수를 출력한다.
• 두 번째 줄에는 각 영역의 크기를 오름차순으로 출력한다.

2. 알고리즘 종류

• 이 문제는 DFS (깊이 우선 탐색) 알고리즘을 사용하여 해결한다. 이 알고리즘을 사용하여 평면을 탐색하며 색칠되지 않은 영역을 찾아 그 크기를 구한다.

3. 주요 부분 및 코드 작성 방법

1. 깊이 우선 탐색(DFS) 사용

• DFS 알고리즘을 사용하여, 시작 지점에서 인접한 모든 색칠되지 않은 영역을 방문한다. 이를 통해 하나의 연결된 구역의 크기를 구한다.

2. 색칠된 직사각형 표시

• 입력으로 주어지는 직사각형 좌표를 이용해, 해당 영역을 true로 표시하여 색칠된 영역임을 나타낸다.

3. 구역 크기 계산 및 정렬

• DFS를 통해 색칠되지 않은 각 구역의 크기를 계산한 후, 이를 리스트에 저장하고 오름차순으로 정렬한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리
  • 평면의 크기 N, M과 색칠된 직사각형의 개수 K를 입력받고, paper 배열을 초기화한다.
• BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.nextToken()); // 평면의 세로 길이 M = Integer.parseInt(st.nextToken()); // 평면의 가로 길이 int K = Integer.parseInt(st.nextToken()); // 직사각형의 개수 paper = new boolean[N][M]; // 평면을 색칠 여부로 나타낼 2차원 배열
• 직사각형 영역 색칠
  • 각 직사각형의 좌표를 읽어와 해당 영역을 true로 설정하여 색칠된 부분을 표시한다.
  • 주어진 좌표는 평면의 좌측 하단 기준이므로, 평면의 세로 길이를 고려하여 위치를 조정한다.
• for (int i = 0; i < K; i++) { st = new StringTokenizer(br.readLine(), " "); int lc = Integer.parseInt(st.nextToken()); // 직사각형의 왼쪽 하단 X 좌표 int lr = N - Integer.parseInt(st.nextToken()) - 1; // 직사각형의 왼쪽 하단 Y 좌표 int rc = Integer.parseInt(st.nextToken()) - 1; // 직사각형의 오른쪽 상단 X 좌표 int rr = N - Integer.parseInt(st.nextToken()); // 직사각형의 오른쪽 상단 Y 좌표 for (int r = rr; r <= lr; r++) { // 직사각형의 Y 범위 for (int c = lc; c <= rc; c++) { // 직사각형의 X 범위 paper[r][c] = true; // 직사각형 부분을 true로 표시하여 색칠된 영역임을 나타냄 } } }
• 색칠되지 않은 영역 탐색 및 결과 저장
  • 전체 평면을 탐색하면서 색칠되지 않은 영역을 발견하면 DFS를 호출하여 구역의 크기를 구하고 리스트에 추가한다.
  • 구역의 크기를 오름차순으로 정렬하여 출력한다.
• List<Integer> answer = new ArrayList<>(); // 색칠되지 않은 영역의 크기를 저장할 리스트 for (int i = 0; i < N; i++) { // 전체 평면을 탐색 for (int j = 0; j < M; j++) { cnt = 1; // 각 구역의 크기를 초기화 if (!paper[i][j]) answer.add(dfs(i, j)); // 색칠되지 않은 영역이 있으면 DFS 탐색 } } Collections.sort(answer); // 구역 크기를 오름차순으로 정렬 System.out.println(answer.size()); // 색칠되지 않은 구역의 개수를 출력 for (int i : answer) System.out.print(i + " "); // 각 구역의 크기를 출력

(2) 깊이 우선 탐색 함수 (dfs)

• 영역 탐색 및 크기 계산
  • 현재 위치에서 인접한 네 방향으로 탐색을 진행한다.
  • 색칠되지 않은 영역이면 재귀적으로 탐색을 계속하고, 방문한 위치를 true로 표시하여 중복 방문을 방지한다.
  • 탐색을 완료한 후, 구역의 크기를 반환한다.
• public static int dfs(int r, int c) { paper[r][c] = true; // 현재 위치를 방문 처리 for (int i = 0; i < 4; i++) { // 상하좌우 네 방향 탐색 int nr = r + dr[i]; int nc = c + dc[i]; if (nr < 0 || nc < 0 || nr >= N || nc >= M || paper[nr][nc]) continue; // 경계를 벗어나거나 이미 방문한 경우 paper[nr][nc] = true; // 방문한 위치를 true로 설정 cnt = dfs(nr, nc) + 1; // 재귀적으로 탐색하며 영역 크기를 증가시킴 } return cnt; // 최종적으로 구한 구역의 크기를 반환 }

5. 전체 코드

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

public class BOJ2583 {
    static int N, M, cnt; // 평면의 크기와 각 구역의 크기를 저장할 변수
    static boolean[][] paper; // 평면의 색칠 여부를 나타내는 2차원 배열
    static int[] dr = {-1, 1, 0, 0}; // 행 이동 (상, 하)
    static int[] dc = {0, 0, -1, 1}; // 열 이동 (좌, 우)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 생성
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 첫 번째 줄 입력을 공백 기준으로 분리하여 토큰화

        N = Integer.parseInt(st.nextToken()); // 평면의 세로 길이
        M = Integer.parseInt(st.nextToken()); // 평면의 가로 길이
        int K = Integer.parseInt(st.nextToken()); // 직사각형의 개수
        paper = new boolean[N][M]; // 평면 초기화 (색칠 여부 저장)

        // 직사각형 색칠 처리
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine(), " "); // 직사각형 좌표 입력
            int lc = Integer.parseInt(st.nextToken()); // 왼쪽 하단 X 좌표
            int lr = N - Integer.parseInt(st.nextToken()) - 1; // 왼쪽 하단 Y 좌표 (세로 기준 반전)
            int rc = Integer.parseInt(st.nextToken()) - 1; // 오른쪽 상단 X 좌표
            int rr = N - Integer.parseInt(st.nextToken()); // 오른쪽 상단 Y 좌표 (세로 기준 반전)
            for (int r = rr; r <= lr; r++) { // 직사각형의 Y 범위 내
                for (int c = lc; c <=

 rc; c++) { // 직사각형의 X 범위 내
                    paper[r][c] = true; // 직사각형 부분을 true로 설정하여 색칠됨을 표시
                }
            }
        }

        List<Integer> answer = new ArrayList<>(); // 색칠되지 않은 영역의 크기를 저장할 리스트
        for (int i = 0; i < N; i++) { // 평면 전체 탐색
            for (int j = 0; j < M; j++) {
                cnt = 1; // 각 구역의 크기 초기화
                if (!paper[i][j]) answer.add(dfs(i, j)); // 색칠되지 않은 영역 발견 시 DFS 탐색
            }
        }
        Collections.sort(answer); // 구역 크기를 오름차순으로 정렬
        System.out.println(answer.size()); // 색칠되지 않은 구역의 개수 출력
        for (int i : answer) System.out.print(i + " "); // 각 구역의 크기 출력
    }

    // 깊이 우선 탐색(DFS) 함수
    public static int dfs(int r, int c) {
        paper[r][c] = true; // 현재 위치를 방문 처리
        for (int i = 0; i < 4; i++) { // 네 방향(상, 하, 좌, 우)으로 탐색
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M || paper[nr][nc]) continue; // 경계 체크 및 방문 여부 확인
            paper[nr][nc] = true; // 새로운 위치 방문 처리
            cnt = dfs(nr, nc) + 1; // 재귀 호출을 통해 연결된 영역의 크기를 증가
        }
        return cnt; // 구역 크기 반환
    }
}