[백준 27211번] 파이썬 - 도넛 행성

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

27211번: 도넛 행성

 

 

# 조건

 

• 준겸이는 N×M칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다. 
• 준겸이는 본인의 집이 있는 위치를 기준으로 삼아 (0,0)이라고 표시하기로 했다.
• 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸 걸어가면, 위치 (0,1)에 도달할 것이다.
• 마찬가지로 아래로 한 칸 걸어가면, 위치 (1,0)에 도달할 것이다. 준겸이가 (0,0)에서 M칸 오른쪽으로 걸어가면, 한 바퀴를 돌아 다시 원래 자리로 되돌아오게 된다.
• 비슷하게 (0,0)에서 N칸 아래로 걸어가면, (0,0)으로 돌아오게 된다. 행성은 연결되어 있기 때문에, 준겸이가 (0,0)에서 왼쪽으로 한 칸 걸어가면 위치 (0,M−1)에 도달할 것이다. 마찬가지로 준겸이가 (0,0)에서 위로 한 칸 걸어가면 (N−1,0)에 도달하게 된다.
• 준겸이는 행성을 탐험하려고 한다. 만약 준겸이가 비어 있는 어떤 칸 A=(p1,q1)에서 시작해, 숲에 막히지 않고 비어 있는 칸 B=(p2,q2)에 도달할 수 있다면 A와 B는 같은 구역이다.
• 반대로, 도달할 수 없다면 A와 B는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.

 

 

# 예제

# input
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

# output
2

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

 

# 접근 방법

• 0이 있는 칸을 찾아 bfs 함수를 실행해준다.
• 도넛 모양이기 때문에, 행 또는 열이 0 미만이 되거나 격자 크기를 벗어난다면, 그에 맞는 인덱스로 바꿔 주어야 된다.
• 인덱스가 - 가 된다면 행 또는 열에서 그만큼 빼주면 되고
• 최대 크기를 벗어난다면 벗어난 인덱스 크기에서 최대 크기만큼 빼주면 된다.

if ni < 0:  
    ni = N + ni  
elif ni >= N:  
    ni = ni-N  
if nj < 0:  
    nj = M + nj  
elif nj >= M:  
    nj = nj-M

• 이후 탐색하며 1로 바꾸어 주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
def bfs(x, y):  
    q = deque()  
    q.append((x,y))  
    while q:  
        sti, stj = q.popleft()  
        for i in range(4):  
            ni, nj = sti + di[i], stj + dj[i]  
            if ni < 0:  
                ni = N + ni  
            elif ni >= N:  
                ni = ni-N  
            if nj < 0:  
                nj = M + nj  
            elif nj >= M:  
                nj = nj-M  
            if planet[ni][nj] == 0:  
                q.append((ni, nj))  
                planet[ni][nj] = 1  
  
  
di, dj = [1,-1,0,0], [0,0,1,-1]  
  
N, M = map(int, input().split())  
planet = [[*map(int, input().split())] for _ in range(N)]  
  
cnt = 0  
for i in range(N):  
    for j in range(M):  
        if planet[i][j] == 0:  
            bfs(i, j)  
            cnt += 1  
  
print(cnt)