[백준][Python][2583][BFS] 영역 구하기

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

2583번: 영역 구하기

BFS 문제다.

입력에 맞게 벽을 맵에 넣는것, 출력이 살짝 다른것 빼고

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

2667번: 단지번호붙이기

이문제랑 똑같다.

import sys
from collections import deque


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


n, m, k = [int(i) for i in sys.stdin.readline().split()]

d = [[1]*m for _ in range(n)]
for _ in range(k):
    ax, ay, bx, by = [int(i) for i in sys.stdin.readline().split()]

    for i in range(ax, bx):
        for j in range(ay, by):
            d[j][i] = 0

v = [[False]*m for _ in range(n)]

ret = 0
val = []
for i in range(n):
    for j in range(m):
        q = deque()
        block = deque()
        if v[i][j] == True or d[i][j] == 0:
            continue

        v[i][j] = ret
        q.append((i, j))
        block.append((i, j))
        while q:
            y, x = q.popleft()
            v[y][x] = True
            for a in range(4):
                cy, cx = y+dy[a], x+dx[a]
                if 0 <= cy < n and 0 <= cx < m:
                    if v[cy][cx] == False and d[cy][cx] == 1:
                        q.append((cy, cx))
                        block.append((cy, cx))
                        v[cy][cx] = True
        ret = ret + 1
        val.append(len(block))
print(ret)
print(" ".join(str(i) for i in sorted(val)).strip())