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

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

2583번: 영역 구하기

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

m,n,k=map(int, input().split())
info=[]
for _ in range(k):
    info.append(list(map(int,input().split())))

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

for item in info:
    start_x, start_y, end_x, end_y = item
    for x in range(start_x,end_x):
        for y in range(start_y,end_y):
            graph[x][y]=1

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

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


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

result.sort()

print(len(result))
for i in result:
    print(i,end=' ')

0으로 채워진 배열(graph)에 직사각형이 그려진 곳은 1로 채운다.

그리고 그래프가 0인공간마다 bfs함수를 실행해서 빈공간의 수(result)를 세며 방문한 곳은 1로 채운다.

result값을 리스트에 추가하고 정렬한뒤 프린트한다.