[백준] 2583번 영역 구하기

💡문제접근

• BFS 탐색을 이용해서 문제를 해결했다. 해당 영역에 속하는 부분을 1로 카운팅하고 0으로 카운팅된 값의 개수를 세어주면 되는 비교적 간단한 그래프 문제였다.

💡코드(메모리 : 34200KB, 시간 : 68ms)

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

def BFS(a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 1
    area = 1
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    while queue:
        y, x = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= ny < M and 0 <= nx < N and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                queue.append((ny, nx))
                area += 1
    return area

M, N, K = map(int, input().strip().split())
graph = [[0 for _ in range(N)] for _ in range(M)]
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().strip().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1

res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            val = BFS(i, j)
            res.append(val)
            graph[i][j] = 1
res.sort()
print(len(res))
print(*res)

💡소요시간 : 12m