BFS를 사용하여 해결,,
처음엔 DFS로 풀려다가 DFS는 최단경로임을 보장할 수 없다는 것을 까먹음,.
어떻게 이걸 까먹을 수 있을까 싶으면서
꾸준히 해야하는 것의 중요성을 다시한번 깨닫는 순간😥
import sys
from collections import deque
global N
global M
global data
N, M = map(int, sys.stdin.readline().rstrip().split(' '))
data = [list(input()) for i in range(N)]
visit = [[0 for i in range(M)] for j in range(N)]
def BFS(x, y, visit):
queue = deque()
queue.append([x, y])
#상, 우 , 하, 좌
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
visit[x][y] = 1
while queue:
[x, y] = queue.popleft()
if x == N-1 and y == M-1:
return visit[x][y]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx <= N-1 and 0 <= ny <= M-1 and data[nx][ny] == "1" and visit[nx][ny] == 0:
queue.append([nx, ny])
#변화된 좌표까지의 최단 길이
visit[nx][ny] = visit[x][y]+1
print(BFS(0, 0, visit))
visit은 해당 좌표까지 가장 짧은 경로의 길이를 담고 있음