[백준-2583] 영역 구하기 / Python

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

from collections import deque

m, n, k = map(int, input().split())
graph = [[0] * n for i in range(m)]

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

l = []

for i in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for j in range(x1, x2):
        for k in range(y1, y2):
            graph[k][j] = 1


def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    graph[x][y] = 1
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    cnt += 1
                    queue.append([nx, ny])
    l.append(cnt)


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

print(len(l))
l.sort()
print(*l)

 

해설

그래프이론 분류로 들어가서 픽한 문제였는데 단순한 BFS 문제였다. 여태까지 그래프 관련 문제는 대부분 BFS나 다익스트라로 해결할 수 있었던 것 같았다.

이 문제에서 채워져있는 직사각형을 어떻게 처리할까 잠깐 고민했지만 어렵지 않게 해결했다.

나머지는 간단하게 BFS 알고리즘을 이용해 해결할 수 있었다.😀