[백준] 27211 - 도넛 행성 / Python / 골드5

🚩문제 주소

📄풀이

그래프 탐색 -> BFS

이 문제는 상하좌우를 움직여서 그래프를 탐색하는 일반적인 BFS 문제에서 한 가지 테크닉이 추가된 문제입니다.
주어진 그래프의 끝을 벗어나면 무시하는 것이 아니라 처음이나 끝으로 되돌아가게 풀어야 합니다.

nx = (nx + N) % N
ny = (ny + M) % M

예를 들어, 가로 길이가 6, 세로 길이가 5로 주어진 그래프에서 좌표 (0, 0)에서 왼쪽으로 간다면 (-1, 0)이 될 것입니다.
일반적인 문제라면 제한을 벗어났으므로 무시하고 다른 방향을 탐색하겠지만 여기선 가로 길이만큼 더해준 후 다시 가로 길이로 나눈 나머지로 바꿔줍니다.
(-1 + 6) % 6 = 5 -> (5, 0) (끝의 좌표)

계속 탐색하다가 상, 하, 좌, 우 방향에 갈 곳이 없다면 탐색을 종료하게 됩니다.
탐색이 종료되면 구역 하나를 탐색한 것이므로 정답을 +1 합니다.

👨‍💻코드

from collections import deque

def bfs(a, b):
  q = deque()
  q.append([a, b])
  visited[a][b] = 1

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + move[i][0]
      ny = y + move[i][1]
      nx = (nx + N) % N
      ny = (ny + M) % M
      if not visited[nx][ny] and planet[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append([nx, ny])

N, M = map(int, input().split())
planet = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
move = [[0,1],[0,-1],[1,0],[-1, 0]]
answer = 0

for i in range(N):
  for j in range(M):
    if planet[i][j] == 0 and not visited[i][j]:
      bfs(i, j)
      answer += 1

print(answer)