둔필승총

https://www.acmicpc.net/problem/2178

[문제 풀이]

(1,1)에서 출발하여 (N,M)까지 가는 길 중 최소의 칸 수를 가야하는 길을 구해야 한다. 이 문제는 1인 영역만 일단 지나도록 설계한다. 1인 지역을 지나갈때 그 전의 지역의 graph 수에서 1을 추가해준다. 그렇게 하면 graph의 (N,M) 좌표를 출력하면 몇게의 길을 지나왔는지 알 수 있다. 나는 BFS를 통해 풀었다.

from collections import deque
n,m = map(int,input().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))
def bfs(a,b):
    q=deque()
    q.append((a,b))
    dx=[-1,1,0,0]
    dy=[0,0,1,-1]
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=graph[x][y]+1
bfs(0,0)
print(graph[n-1][m-1])