문제
N×M크기의 배열로 표현되는 미로가 있다.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
내 풀이
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
maze = [list(map(int, input().strip())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def BFS(x, y):
q = deque()
q.append((x, y))
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1
q.append((nx, ny))
return maze[n-1][m-1]
print(BFS(0, 0))코멘트
지나야 하는 최소의 칸 수를 출력하는 것이므로 너비 우선 탐색을 이용하면 된다. 그러나 우리가 흔히 아는 트리 형태가 아니라 2차원 배열을 탐색하는 것이라 어떻게 코드를 구현해야할지 어려웠다.
우선 이동 방향이 상하좌우로 4가지가 되므로 이동 방향인 (0, 1), (0, -1), (-1, 0), (1, 0)을 dx와 dy로 선언을 해두고, BFS를 돌 때마다 4가지 좌표 이동을 해 준 뒤 이동한 칸에 1이 있으면 2로 만들어주고, 0이면 아무 활동도 하지 않는다. 따라서 여기서는 굳이 visited 배열을 선언하지 않고도 방문 상태를 표시할 수 있다.
References
