[BOJ 27211] 도넛 행성 - Python 풀이

링크

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

문제

준겸이는 N×M$N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다.

준겸이는 본인의 집이 있는 위치를 기준으로 삼아 (0,0)$(0,0)$이라고 표시하기로 했다. 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸 걸어가면, 위치 (0,1)$(0,1)$에 도달할 것이다. 마찬가지로 아래로 한 칸 걸어가면, 위치 (1,0)$(1,0)$에 도달할 것이다. 준겸이가 (0,0)$(0,0)$에서 M$M$칸 오른쪽으로 걸어가면, 한 바퀴를 돌아 다시 원래 자리로 되돌아오게 된다. 비슷하게 (0,0)$(0,0)$에서 N$N$칸 아래로 걸어가면, (0,0)$(0,0)$으로 돌아오게 된다. 행성은 연결되어 있기 때문에, 준겸이가 (0,0)$(0,0)$에서 왼쪽으로 한 칸 걸어가면 위치 (0,M−1)$(0,M-1)$에 도달할 것이다. 마찬가지로 준겸이가 (0,0)$(0,0)$에서 위로 한 칸 걸어가면 (N−1,0)$(N-1, 0)$에 도달하게 된다.

준겸이는 행성을 탐험하려고 한다. 만약 준겸이가 비어 있는 어떤 칸 A=(p1,q1)$A=(p_1,q_1)$에서 시작해, 숲에 막히지 않고 비어 있는 칸 B=(p2,q2)$B=(p_2,q_2)$에 도달할 수 있다면 A$A$와 B$B$는 같은 구역이다. 반대로, 도달할 수 없다면 A$A$와 B$B$는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.

입력

첫 번째 줄에 N$N$과 M$M$이 공백을 사이에 두고 주어진다.

두 번째 줄부터 N$N$개의 줄에 걸쳐 N×M$N \times M$개의 칸에 대한 정보가 주어진다. 두 번째 줄에서부터 i$i$번째 줄에 주어지는 j$j$번째 정수는 칸 (i−1,j−1)$(i-1, j-1)$에 대한 정보이다. 만약 0이라면 비어 있는 것이고, 1이라면 숲으로 막혀 있는 것이다.

출력

탐험할 수 있는 구역의 개수를 출력한다.

제한

•  2≤N≤1000$2 \le N \le 1\,000$ 
•  2≤M≤1000$2 \le M \le 1\,000$ 

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
grid = list(list(map(int, sys.stdin.readline().split())) for _ in range(N))
visited = [[False] * M for _ in range(N)]
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
cnt = 0

def can_go(x, y):
    if visited[x][y]: return False
    if grid[x][y] == 1: return False
    return True

# 도넛형태의 좌표를 구하는 함수
def get_pos(x, y):
    new_x, new_y = x, y
    
    if x < 0: new_x = N-1
    elif x >= N: new_x = 0
    
    if y < 0: new_y = M-1
    elif y >= M: new_y = 0
    
    return new_x, new_y

def bfs(x, y):
    global cnt
    
    cnt += 1
    q = deque()
    visited[x][y] = True
    q.append((x, y))

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

        for i in range(4):
            new_x, new_y = get_pos(x+dx[i], y+dy[i])

            if can_go(new_x, new_y):
                visited[new_x][new_y] = True
                q.append((new_x, new_y))

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

print(cnt)

풀이

쇼미더코드 3회차 문제 중 가장 쉬웠다. BFS를 사용했고 그 과정에서 x좌표가 0보다 작을 경우 N-1로, y좌표가 0보다 작은 경우 M-1로, x좌표가 N보다 크거나 같을 경우 0으로, y좌표가 M보다 크거나 같을 경우 0으로 만들어주는 것을 제외하고는 특별한 것은 없었다.