[백준] 27211번 - 도넛 행성 (Python, 파이썬)

문제

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

27211번: 도넛 행성

 

접근 방법

BFS 또는 DFS를 이용하여 풀면 된다.

아직 방문하지 않은 곳 하나를 찾고 이를 기준으로 막혀있지 않은 다른 인접 구역들을 모두 방문하면 이들을 다 합쳐 하나의 구역이 된다.

이후 방문하지 않은 다른 곳을 하나 찾아 이러한 과정을 반복하면 된다.

양쪽 끝이 연결되어 있다는 특이점이 있는데, arr[i][j]에 접근하는 대신 arr[i % N][j % M]으로 접근하도록 하면 (0, M-1) 오른쪽이 (0, 0), (0, 0) 왼쪽이 (0, M-1)이 되므로 자연스럽게 해결된다. (위/아래도 마찬가지)

 

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().rstrip().split())
mapArr = []
for i in range(N):
    mapArr.append(list(map(int, sys.stdin.readline().rstrip().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer = 0
for i in range(N):
    for j in range(M):
        if mapArr[i][j] == 0: # 빈 구역을 찾으면 1로 칠하고 인접한 구역 모두 1로 칠함
            answer += 1
            
            tempQueue = deque()
            tempQueue.append((i, j))
            mapArr[i][j] = 1
            
            while tempQueue:
                currentI, currentJ = tempQueue.popleft()
                for x in range(len(dx)):
                    nextI = currentI + dx[x]
                    nextJ = currentJ + dy[x]
                    
                    if mapArr[nextI % N][nextJ % M] == 0:
                        mapArr[nextI % N][nextJ % M] = 1
                        tempQueue.append((nextI % N, nextJ % M))

print(answer)