백준 27211 도넛 행성 python (쇼미더코드: 원티드 주관 코딩테스트 대회 2022년 3회차 A번)

문제 바로가기

문제

준겸이는 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는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.

입력

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

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

출력

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

풀이

n, m = map(int, input().split())
maps = []
for i in range(n):
    maps.append(list(map(int, input().split())))
# 영역의 크기와 영역의 상태를 입력받아줍니다.
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 4방위 이동을 설정해줍니다.
def walk(a, b):
    stack = []
    stack.append((a, b))
    while stack:
        x, y = stack.pop()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx == n:
                nx = 0
            elif nx < 0:
                nx = n - 1
            elif ny == m:
                ny = 0
            elif ny < 0:
                ny = m - 1
            # 도넛형으로 연결되어있으므로 범위보다 커지면 0으로 돌아가고
            # 0보다 작아지면 뒤 영역으로 돌아가줍니다.
            if not maps[nx][ny]:
                maps[nx][ny] = 1
                stack.append((nx, ny))
            # 이동한 자리가 연결되어 있으면 이동해줍니다.
            # 이를 통해 연결된 모든 영역을 탐험해줍니다.
cnt = 0
for i in range(n):
    for j in range(m):
        if not maps[i][j]:
            walk(i, j)
            cnt += 1
            # 탐험이 가능하면 횟수를 더해줍니다.

print(cnt)
# 몇 번의 탐험이 되는지 확인해줍니다.