백준 #27211 도넛 행성

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
from collections import deque


def bfs(i, j):
    visited[i][j] = True
    q = deque()
    q.append((i, j))

    while q:
        r, c = q.popleft()
        for k in range(4):
            nr = (r + dr[k]) % n
            nc = (c + dc[k]) % m
            if arr[nr][nc] == 0 and not visited[nr][nc]:
                q.append((nr, nc))
                visited[nr][nc] = True
    return

n, m = map(int, input().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
cnt = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0 and not visited[i][j]:
            bfs(i, j)
            cnt += 1

print(cnt)

풀이

기본적인 BFS문제이다. 도넛은 둥글어서 배열 범위를 벗어나도 되기때문에 나머지 연산을 통해서 인덱스에러를 피해주었다. visited 배열을 통해 중복 방문을 피해주고 bfs가 실행 될 때마다 카운트를 해주어서 정답을 구했다.