[boj] 백준 2583 영역 구하기 python 풀이(bfs)

문제

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

2583번: 영역 구하기

 

문제 풀이

문제에서 주어진 좌표가 일반적인 이차원배열 인덱스와 반대인 것만 잘 체크해주면 되는 bfs 문제

 

코드

import sys
input = sys.stdin.readline
import collections

def fill_MAP(MAP, x,y,rx,ry):
    for i in range(M-ry, M-y):
        for j in range(x, rx):
            MAP[i][j] = 1

def bfs(MAP, sx, sy):
    move = {(-1,0), (0,1), (1,0), (0,-1)}
    q = collections.deque()
    q.append((sx,sy))

    MAP[sx][sy] = 1
    cnt = 1
    while q:
        cx,cy = q.popleft()

        for tx, ty in move:
            nx = tx + cx
            ny = ty + cy

            if 0<=nx<M and 0<=ny<N and MAP[nx][ny] == 0:
                q.append((nx,ny))
                MAP[nx][ny] = 1
                cnt += 1

    return cnt


M, N, K = map(int,input().split())
MAP = [[0 for _ in range(N)] for _ in range(M)]
for _ in range(K):
    x,y, rx, ry = map(int,input().split())
    fill_MAP(MAP, x,y,rx,ry)

res = []
for i in range(M):
    for j in range(N):
        if MAP[i][j] == 0:
            res.append(bfs(MAP, i,j))

print(len(res))
print(*sorted(res))