문제

도넛 행성은 행과 열이 양 끝에서 이어진 격자 행성이다. 숲으로 둘러싸인 공터의 개수를 구하는 문제이다.

풀이

BFS/DFS를 사용하여 연결된 공터를 세는 문제이다. 행과 열이 양 끝에서 이어지므로 모듈로 연산을 사용한다.

코드

from collections import deque

N, M = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(N)]

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))


def bfs(x, y):
    q = deque([(x, y)])

    while q:
        x, y = q.popleft()

        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            nx %= N
            ny %= M

            if grid[nx][ny] == 1:
                continue

            grid[nx][ny] = 1
            q.append((nx, ny))

    return 1


result = 0

for x in range(N):
    for y in range(M):
        if grid[x][y] == 1:
            continue

        result += bfs(x, y)

print(result)

시간 복잡도

O(N × M)