[백준][BFS] 2583. 영역 구하기

2583. 영역 구하기

2583번: 영역 구하기

 

• 영역을 미리 다 체크해두고 아닌 부분만 계산

from collections import deque

m, n, k = map(int, input().split())
graph = [[0 for _ in range(n)] for _ in range(m)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(x1, x2):
        for j in range(y1, y2):
            graph[j][i] = 1

result = []


def bfs(i, j):
    queue = deque()
    tmp = 1

    queue.append((i, j))
    graph[i][j] = 1

    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]

            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                continue
            graph[nx][ny] = 1
            tmp += 1
            queue.append((nx, ny))

    result.append(tmp)


for i in range(m):
    for j in range(n):
        if graph[i][j] == 1:
            continue
        bfs(i, j)

print(len(result))
print(*sorted(result))