백준 2583. 영역 구하기

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

import sys
from collections import deque
input = sys.stdin.readline

# 입력 받기
M, N, K = map(int, input().split())
paper = [[0] * N for _ in range(M)]  # 종이 배열

# 직사각형 채우기
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):  # y 좌표 범위
        for j in range(x1, x2):  # x 좌표 범위
            paper[i][j] = 1  # 색칠된 영역 표시

# 방향 벡터 (상하좌우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# BFS 함수
def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    paper[start_x][start_y] = 1  # 방문 처리
    area_size = 1  # 현재 영역의 넓이 초기화

    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and paper[nx][ny] == 0:  # 미방문 칸
                paper[nx][ny] = 1  # 방문 처리
                queue.append((nx, ny))
                area_size += 1

    return area_size

# 전체 영역 탐색
areas = []
for i in range(M):
    for j in range(N):
        if paper[i][j] == 0:  # 색칠되지 않은 영역 발견
            areas.append(bfs(i, j))

# 결과 출력
areas.sort()  # 넓이 오름차순 정렬
print(len(areas))  # 영역 개수
print(*areas)  # 각 영역의 넓이

[체크포인트]

1. 빈 이차원 배열에 직사각형 범위만큼 전부 1로 채우기

2. 전체 영역을 탐색하면서 빈 공간을 발견하면 그곳부터 bfs 돌려서 그 영역의 범위 구한 후 리스트에 추가하기

3. 그 리스트의 len이 영역 개수, 그 리스트에 범위 다 들어가있으니 정렬 후 출력하면 끝!