백준 2583번 - 영역 구하기

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

rects = []
n,m,k = map(int, input().split())
for _ in range(k):
    x1,y1,x2,y2 = map(int, input().split())
    rects.append((x1,y1,x2,y2))

dx = [0,0,-1,1]
dy = [-1,1,0,0]

answer = []
graph = [[0] * m for _ in range(n)]

for x1,y1,x2,y2 in rects:
    for y in range(y1,y2):
        for x in range(x1,x2):
            i = n-1-y
            j = x
            graph[i][j] = 1

visited = [[False] * m for _ in range(n)]

def bfs(sx,sy):
    q = deque([(sx,sy)])
    visited[sx][sy] = True
    count = 1

    while q:
        x,y = q.popleft()
        for d in range(4):
            nx = dx[d]+x
            ny = dy[d]+y
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and graph[nx][ny] == 0:
                visited[nx][ny] = True
                q.append((nx,ny))
                count+=1
    return count

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0 and not visited[i][j]:
            answer.append(bfs(i,j))

answer.sort()
print(len(answer))
print(*answer)