[BOJ] 2583. 영역 구하기(Python) / BFS

www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

# 22분 소요

 

아주 간단한 BFS 문제

• M*N크기 맵 1로 초기화
• Input 받은 내용을 미리 M*N크기의 맵에 0으로 그려줌
• 이후 맵에서 1일 때 연결된 곳 BFS 이용하여 0으로 지워주면서 갯수 셈
• 연결된 곳 0으로 지우는 작업 끝날 때마다 resut += 1, parts에는 갯수 append 해주고, 마지막 출력할 때 sort

 

파이썬 코드는 다음과 같다.

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs(sr, sc):
    Q = deque([(sr, sc)])
    A[sr][sc] = 0
    cnt = 1
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < M and 0 <= nc < N) or not A[nr][nc]:
                continue
            if A[nr][nc]:
                A[nr][nc] = 0
                Q.append((nr, nc))
                cnt += 1
    return cnt

# main
M, N, K = map(int, input().split())
A = [[1] * N for _ in range(M)]
for _ in range(K):
    c1, r1, c2, r2 = map(int, input().split())
    for r in range(r1, r2):
        for c in range(c1, c2):
            A[r][c] = 0
result = 0
parts = []
for i in range(M):
    for j in range(N):
        if A[i][j]:
            parts.append(bfs(i, j))
            result += 1
print(result)
print(*sorted(parts))

---

• 고찰 : 큰 고민 없이 금방 풀 수 있는 BFS 문제였다. Keep Going!