2593-백준-영역 구하기

1. 문제 출처

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

2583번: 영역 구하기

2. 풀이

간단한 bfs문제이다.

from collections import deque
# 입력
m,n,k = map(int,input().split())
# 상하좌우 이동
dx = [0,0,-1,1]
dy = [-1,1,0,0]
# 방문 리스트
visted = [[0]*m for _ in range(n)]
# 너비 리스트
area_list = []
# 직사각형 그리기 
for _ in range(k):
    x,y,xx,yy = map(int,input().split())
    for i in range(x,xx):
        for j in range(y,yy):
            visted[i][j] = (-1)
# 방문하지 않으면  해당 좌표부터 bfs를 실시하여 영역 채우기
for i in range(n):
    for j in range(m):
        if visted[i][j] == 0 :
            # 사각형 하나에 너비가 1이므로 인접한 사각형 하나당 1씩 더하기
            area = 1
            visted[i][j] = 1
            queue = deque([[i,j]])
            while queue:
                x,y = queue.popleft()
                for idx in range(4):
                    xx = x + dx[idx]
                    yy = y + dy[idx]
                    if 0<=xx<n and 0<=yy<m:
                        if visted[xx][yy] == 0:
                            visted[xx][yy] = 1
                            queue.append([xx,yy])
                            area+=1
            area_list.append(area)
area_list.sort()
# 출력
print(len(area_list))     
for area in area_list:
    print(area,end = " ")