[BOJ] 2583. 영역 구하기

📌 문제 제목

문제 링크: BOJ 2583

---

🗒️ 문제 설명

M x N 크기의 모눈종이가 있을 때, 이 모눈종이 위에 K개의 직사각형을 그리고 남은 부분의 영역 개수와 크기를 구하여라

시간 제한: 1초

메모리 제한: 128MB

1 <= M, N, K <= 100

---

💡 문제 해결 아이디어

• M x N 크기의 True 값을 가지는 graph 배열을 만든다.
• K번 직사각형을 만드면서 graph에 False 값을 넣는다.
• BFS를 수행하며 영역의 크기와 개수를 구한다.

---

⌛️ 시간 복잡도

• O(M x N + K)

---

✅ 최종 코드

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

M, N, K = map(int, input().split())
graph = [[True] * N for _ in range(M)]

for _ in range(K):
    l_y, l_x, r_y, r_x = map(int, input().split())

    for i in range(l_x, r_x):
        for j in range(l_y, r_y):
            graph[i][j] = False

visited = [[False] * N for _ in range(M)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(graph, x, y, visited) -> int:
    queue = deque([(x, y)])
    visited[x][y] = True
    area = 1
    while queue:
        xp, yp = queue.popleft()
        for dx, dy in direction:
            nx, ny = xp + dx, yp + dy
            if not (0 <= nx < M and 0 <= ny < N):
                continue
            if graph[nx][ny] and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
                area += 1
    return area


answer = 0
areas = []
for i in range(M):
    for j in range(N):
        if graph[i][j] and not visited[i][j]:
            area = bfs(graph, i, j, visited)
            areas.append(area)
            answer += 1
areas.sort()
print(answer)
print(*areas)