2583번: 영역 구하기

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있습니다. 이 모눈종이 위에 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어집니다. 분리된 각 영역의 개수와, 각 영역의 넓이를 오름차순으로 정렬하여 출력하는 문제입니다.

• 입력: 첫째 줄에 M(세로), N(가로), 그리고 직사각형의 개수 K가 주어집니다. 둘째 줄부터 K개의 줄에 직사각형의 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)가 주어집니다.
• 출력: 첫째 줄에 분리된 영역의 개수를 출력하고, 둘째 줄에 각 영역의 넓이를 오름차순으로 정렬하여 공백으로 구분해 출력합니다.

링크: https://www.acmicpc.net/problem/2583

풀이

주어진 직사각형 영역을 2차원 배열에 표시한 뒤, 칠해지지 않은 나머지 영역(0)을 찾아 그래프 탐색(DFS 또는 BFS)을 수행하는 문제입니다.

1. 배열 매핑 및 직사각형 색칠: 문제의 일반적인 좌표계는 왼쪽 아래가 (0,0)이지만, 배열의 인덱스는 왼쪽 위가 (0,0)입니다. 하지만 상하 반전이 일어나더라도 덩어리의 개수와 각각의 넓이는 변하지 않으므로, 주어진 x, y 좌표를 그대로 배열의 인덱스(y를 행, x를 열)로 사용하여 직사각형을 칠해(a[i][j] = 1)도 무방합니다. 주의할 점은 좌표 x1부터 x2-1, y1부터 y2-1까지만 칠해야 칸 단위로 정확히 면적이 계산된다는 것입니다.
2. 영역 탐색 (DFS): 배열 전체를 순회하며 칠해지지 않고(a[i][j] == 0) 아직 방문하지 않은(!visited[i][j]) 칸을 찾습니다. 새로운 빈 영역을 발견하면 정답 변수(ans)를 1 증가시키고, DFS를 호출하여 해당 영역의 넓이를 구합니다.
3. 넓이 계산 (재귀): dfs 메서드는 방문 처리를 한 뒤 초기 넓이를 1로 설정합니다. 상하좌우를 탐색하며 조건에 맞는 빈칸을 발견할 때마다 재귀 호출의 반환값을 누적하여 더합니다. 탐색이 모두 종료되면 완성된 덩어리의 총 넓이를 반환합니다.
4. 결과 정렬 및 출력: 각 영역의 넓이를 List에 담아 탐색을 모두 마친 후 오름차순으로 정렬(Collections.sort)하여 출력합니다.

코드

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

public class Main {
    static int n, m;
    static int[][] a;
    static boolean[][] visited;
    
    // 상하좌우 탐색을 위한 델타 배열
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

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

       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken()); // 세로 크기 (M)
       m = Integer.parseInt(st.nextToken()); // 가로 크기 (N)
       int k = Integer.parseInt(st.nextToken()); // 직사각형 개수 (K)

       a = new int[n][m];
       
       // 1. 직사각형 영역 1로 칠하기
       while (k-- > 0) {
          st = new StringTokenizer(br.readLine());
          int x1 = Integer.parseInt(st.nextToken());
          int y1 = Integer.parseInt(st.nextToken());
          int x2 = Integer.parseInt(st.nextToken());
          int y2 = Integer.parseInt(st.nextToken());

          // 꼭짓점 좌표를 칸 단위로 변환하여 채움
          for (int i = y1; i < y2; i++) {
             for (int j = x1; j < x2; j++) {
                a[i][j] = 1;
             }
          }
       }

       int ans = 0; // 분리된 영역의 총 개수
       List<Integer> list = new ArrayList<>(); // 각 영역의 넓이를 담을 리스트
       visited = new boolean[n][m];
       
       // 2. 전체 배열을 순회하며 빈 영역 탐색
       for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
             // 칠해지지 않았고 방문하지 않은 칸을 발견하면 새로운 영역
             if (a[i][j] == 0 && !visited[i][j]) {
                list.add(dfs(i, j)); // DFS로 반환된 넓이를 리스트에 추가
                ans++; // 영역의 개수 증가
             }
          }
       }

       // 3. 영역 개수 출력
       bw.write(ans + "\n");

       // 넓이를 오름차순으로 정렬 후 차례대로 출력
       Collections.sort(list);
       for (int i : list) {
          bw.write(i + " ");
       }

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

    // 연결된 빈 공간의 넓이를 구하여 반환하는 DFS 메서드
    static int dfs(int y, int x) {
       visited[y][x] = true;
       int ret = 1; // 현재 칸의 넓이를 1로 시작

       // 상하좌우 4방향 탐색
       for (int i = 0; i < 4; i++) {
          int ny = y + dy[i];
          int nx = x + dx[i];
          
          // 배열 범위를 벗어나면 무시
          if (ny < 0 || nx < 0 || ny >= n || nx >= m)
             continue;
             
          // 직사각형 내부이거나 이미 방문한 칸이면 무시
          if (a[ny][nx] == 1 || visited[ny][nx])
             continue;
             
          // 인접한 빈칸으로 재귀 호출하며 반환된 넓이를 누적
          ret += dfs(ny, nx);
       }

       return ret;
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)