[Python] 백준 2583 영역 구하기

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

 

문제 분석

• 눈금 간격이 M x N 크기의 모눈종이
• 눈금에 맞춰 K개의 직사각형을 그릴 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어 지는가
• 그리고 각 영역의 넓이는 얼마인가

 

풀이

• 넓이 우선 탐색 (bfs)

 

코드 설계

1. 직사각형 영역 찾기
   • 직사각형 영역 : 1
   • 직사각형 x : 0
2. 영역 찾기 
   • 0이고, 아직 방문하지 않았으면 덱에 넣기
3. 같은 영역의 범위 구하기
   1. 모눈종이의 범위를 벗어나지 않고
   2. 아직 방문하지 않았으며
   3. g 좌표의 값이 0이면 
   4. append → 가능한 영역 : area += 1

 

정답 코드

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

M, N, K = map(int, input().split()) # 세로, 가로, 직사각형 갯수
g = [[0] * N for _ in range(M)]

for _ in range(K) :
    x1, y1, x2, y2 = map(int, input().split())
    for r in range(x1, x2) :
        for c in range(y1, y2) :
            g[c][r] = 1

v = [[False] * N for _ in range(M)]
d = deque()

area_li = []

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

for i in range(M) :
    for j in range(N) :
        if g[i][j] == 0 and not v[i][j] :
            area = 1
            d.append((i, j))
            v[i][j] = True

            while d :
                h, w = d.popleft()

                for k in range(4) :
                    nh = h + dh[k]
                    nw = w + dw[k]

                    if nh < 0 or nh >= M or nw < 0 or nw >= N :
                        continue
                    if v[nh][nw] :
                        continue
                    if g[nh][nw] != 0 :
                        continue

                    area += 1
                    d.append((nh, nw))
                    v[nh][nw] = True

            area_li.append(area)

print(len(area_li))
area_li.sort()
print(' '.join(map(str, area_li)))