[파이썬] 백준 27211 : 도넛 행성 (골드5)

[파이썬] 백준 27211 : 도넛 행성 (골드5)

• 백준 27211 : 도넛 행성 (골드5)

---

풀이

방향성 생각

• 영역의 개수를 BFS/DFS로 세주기.
• 영역 범위를 벗어나면 %연산을 통해서 영역 내부로 처리해주기.

---

파이썬

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

dires = [(1,0),(0,1),(-1,0),(0,-1)]

H,W = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(H)]
V = [[False]*W for _ in range(H)]

def bfs(x,y):

    V[y][x] = True
    Q = deque([(x,y)])
    while Q:
        x,y = Q.popleft()
        for dx,dy in dires:
            nx,ny = (x+dx)%W,(y+dy)%H
            if not arr[ny][nx] and not V[ny][nx]:
                V[ny][nx] = True
                Q.append((nx,ny))

answer = 0
for i in range(H):
    for j in range(W):
        if not arr[i][j] and not V[i][j]:
            answer += 1
            bfs(j,i)
print(answer)

---

코멘트

• 기본문제.