백준 2583 영역 구하기

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

m, n, k = map(int, input().split())
g = [[0] * n for _ in range(m)]
for _ in range(k):
    x0, y0, x1, y1 = map(int, input().split())
    for i in range(y0, y1):
        for j in range(x0, x1):
            g[i][j] = 1
              
check = [[-1] * n for _ in range(m)]

def bfs(u, v):
    q = deque()
    q.append((u, v))
    check[u][v] = 0
    c = 0
    while q:
        x, y = q.popleft()
        c += 1
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < m and 0 <= ny < n:
                if check[nx][ny] == -1 and g[nx][ny] == 0:
                    q.append((nx, ny))
                    check[nx][ny] = 0
    return c
ans = []
cnt = 0
for u in range(m):
    for v in range(n):
        if check[u][v] == -1 and g[u][v] == 0:
            ans.append(bfs(u, v))
            cnt += 1
            
print(cnt)
ans.sort()
print(*ans)

bfs로 영역의 개수 구하고 / 영역 당 개수 구함