알고리즘 재활 8일차

준겸이는 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$ 

예제 입력 1 복사

5 6
1 1 1 1 1 1
1 0 0 0 1 1
1 1 1 1 0 0
1 1 1 1 0 0
1 1 1 1 1 1

예제 출력 1 복사

2

예제 입력 2 복사

7 8
0 0 1 1 0 0 0 0
0 1 1 1 1 0 1 0
1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 0
1 1 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 1 1 1 1 0 0

예제 출력 2 복사

2

직사각형 격자로 보이지만 실제로는 한 바퀴를 돌아 이동할 수 있는 도넛 모양이기 때문에, 빈 영역의 개수는 두 개이다.

from collections import deque

n, m = map(int, input().split())
planet = list(list(map(int, input().split())) for _ in range(n))
# print(planet)

# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]



def transformx(x):
    if x < 0 :
        x = n + x
    elif x > n - 1:
        x = x - n    
    return x

def transformy(y):
    if y < 0 :
        y = m + y
    elif y > m - 1:
        y = y - m    
    return y

cnt = 0
for i in range(n):
    for j in range(m):        
        if planet[i][j] == 0:
           planet[i][j] = 1
           q = deque()
           q.append((i, j))
           while q :
                now_x, now_y = q.popleft()
                for k in range(4):
                    next_x = transformx(now_x + dx[k])
                    next_y = transformy(now_y + dy[k])    
                    if planet[next_x][next_y] == 0 :
                        planet[next_x][next_y] = 1
                        # print("next coord is", [next_x, next_y])   
                        q.append((next_x, next_y))
                if not q :
                    cnt += 1
                    break
                   
            
           
            
print(cnt)  

배울점

이번 문제의 핵심은 BFS이지만 범위를 넘어섰을 때, 계산 가능한 좌표로 전환하는 것이다. 애초에 규칙 자체를 문제에서 알려준 만큼 , 그다지 어려운 문제는 아니였던 것 같다. 한 가지 이상했던 점은 원래는 while문이 끝나고 cnt += 1를 해주려 했는데 에러가 떠서 while문 안에서 q가 비워지면 break하고 cnt += 1를 해주었다. 좌표변환만 이해하면 되어서 쉬웠다.