[탐색/BFS] 백준 2583 영역 구하기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2583번: 영역 구하기

 

 

2. 문제 풀이

 사각형으로 분리된 영역의 개수의 크기를 구하는 문제입니다.

 

2022.07.01 - [Algorithm] - [구현/수학] 백준 2669 직사각형 네개의 합집합의 면적 구하기 - 파이썬(Python)

 위 문제에서 사용했던 방법과 비슷합니다. 미리 모눈종이를 만들어두고, 사각형의 영역만 False로 바꿉니다. 그러면, 사각형이 겹쳐지더라도 문제가 되지 않습니다.

 이후 BFS 탐색을 이용해서 영역의 개수와 크기를 찾아냅니다.

 

 

 

3. 코드

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

# 입력
N, M, K = map(int, input().split())
board = [[True]*M for _ in range(N)]
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            board[i][j] = False

# BFS 탐색
area = []  # 영역
direction = [(1,0), (-1,0), (0,1), (0,-1)]

for i in range(N):
    for j in range(M):
        # 탐색하지 않은 영역이면 BFS 탐색
        if board[i][j]:
            queue = deque([(i, j)])
            board[i][j] = False
            size = 0
            while queue:
                x, y = queue.popleft()
                size += 1
                for dx, dy in direction:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < N and 0 <= ny < M and board[nx][ny]:
                        board[nx][ny] = False
                        queue.append((nx, ny))
            area.append(size)

# 정렬 후 출력
area.sort()
print(len(area))
print(" ".join(map(str, area)))

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS 탐색에 대한 설명과 코드는 위 링크에서 보실 수 있습니다.