[BOJ][Python] 백준 27211번 : 도넛 행성

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

27211번: 도넛 행성

 

쇼미더 코드에서 나온 은근 재미있는 문제였다.

 

보통의 bfs 알고리즘을 통한 그래프 탐색은 0과 N, M 사이의 범위 안에서만 탐색을 했는데,

 

이 문제는 범위가 없고 nx, ny가 끝 지점에 다다랐을 때 다시 처음 지점으로 이동시키면 되었다.

 

문제 자체는 어렵지 않고, 기본 bfs에서 조금만 응용하면 되는 문제이다.

 

코드를 보면 이해가 빠를 것 같다.

 

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

dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx =  a + dx[i]
            ny =  b + dy[i]

            if nx >= N:
                nx = 0
            elif nx <= -1:
                nx = N-1

            if ny >= M:
                ny = 0
            elif ny <= -1:
                ny = M-1

            if graph[nx][ny] == 0 and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx, ny))


N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))

visited = [[0] * M for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(M):
        if visited[i][j] == 0 and graph[i][j] == 0:
            bfs(i, j)
            cnt += 1

print(cnt)