BaekJoon2583_영역 구하기

문제

풀이

BFS를 사용하면 쉽게 풀 수 있는 문제이다.
각 영역들의 좌표를 이용하여 직사각형이 그려진 영역은 1로 채우고 나머지 영역은 0으로 채워둔다.
0으로 채워져 있는 영역의 넓이를 구하고 더 구하지 못할 때 리스트에 추가하는 방식으로 각 영역의 넓이를 리스트에 채우면 된다.

풀이 코드

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

m,n,k = map(int,input().split())

box = [list(map(int,input().split())) for _ in range(k)]

graph = [[0 for _ in range(n)] for _ in range(m)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for i in box:
    lx,ly = i[0],i[1]
    rx,ry = i[2],i[3]

    for i in range(lx,rx):
        for j in range(ly,ry):
            graph[j][i] = 1

volume = []
queue = deque()


for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            v = 1
            graph[i][j] = 1
            queue.append((i,j))
            while queue:
                x,y = queue.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] == 0:
                        graph[nx][ny] = 1
                        v += 1
                        queue.append((nx,ny))
            volume.append(v)
print(len(volume))
volume.sort()
for i in volume:
    print(i, end=' ')