백준 27211 도넛 행성 - 파이썬

 

 

 

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

27211번: 도넛 행성

 

 

 

문제의 그림이 어마무시했는데... 그냥 그래프 탐색 문제였다.

4963번 섬의 개수, 혹은 2667번 단지번호붙이기와 유사한 문제이다.

 

 

유일하게 추가된 조건은 0번 행과 (N-1) 번 행이 연결되어 있고, 0번 열과 (M-1) 번 열이 연결되어 있다는 점이다.

이 조건을 고려해서 인접한 칸을 탐색할 때 0 <= nx < N과 같은 index 제한 조건을 두는 대신, nx % N의 index를 살펴보는 방식으로 문제를 풀었다.

 

또, visited 배열을 따로 만들어주지 않고 그냥 탐색하면 바로바로 지도를 갱신해 줬다.

 

 

DFS와 BFS 중 어느 것을 사용해서 풀어도 상관이 없겠지만 DFS로 풀었다.

 

 

 

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

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

for i in range(N):
    for j in range(M):
        if world_map[i][j]:
            continue

        answer += 1
        stack = [[i, j]]

        while stack:
            x, y = stack.pop()
            
            for n in range(4):
                nx = (x + dx[n]) % N
                ny = (y + dy[n]) % M

                if not world_map[nx][ny]:
                    stack.append([nx, ny])
                    world_map[nx][ny] = 1

print(answer)