[Python] 백준(BOJ) 2583번: 영역 구하기 - bfs

문제

2583번: 영역 구하기

풀이

먼저 인풋으로 들어온 값들을 가지고 2차원 배열을 채워준 후, 

bfs를 통해서 풀었다.

import sys
from collections import deque

# 오른쪽 위 꼭짓점의 좌표는(N,M)이다
# K개의 네모
M, N, K = map(int, sys.stdin.readline().split(" "))

field = [[0 for _ in range(N)] for _ in range(M)]
size = []

# 채우기
for _ in range(K):
    sx, sy, ex, ey = map(int, sys.stdin.readline().split(" "))
    for i in range(ey-sy):
        for j in range(ex-sx):
            field[sy+i][sx+j] = 2

# bfs
queue = deque()
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]
count = 0

# 전체 돌면서 빈칸찾기
for i in range(M):
    for j in range(N):
        if field[i][j] == 0:
            queue.append([i, j])
            field[i][j] = 1
            count += 1
            c = 1

            while queue:
                x, y = queue.popleft()

                for a in range(4):
                    ndr = x + dr[a]
                    ndc = y + dc[a]

                    if 0 <= ndr < M and 0 <= ndc < N and field[ndr][ndc] == 0:
                        queue.append([ndr, ndc])
                        field[ndr][ndc] = 1
                        c += 1

            size.append(c)

print(count)
for i in sorted(size):
    print(i, end=" ")