이번 문제는 다익스트라 알고리즘을 통해 쉽게 해결하였다. 기존의 다익스트라 알고리즘 문제와 똑같이 작성을 하고, 힙에 넣을 다음 탐색 구역이 1일 경우에는 비용을 1 증가시켜주고, 그 외에는 비용을 그대로 유지한 상태로 진행시킨다. 이렇게 하면 목적지의 최소 비용을 구할 수 있게 된다.

• n, m을 입력받는다.
• 미로를 입력받을 maze 리스트를 선언한다.
• m번 반복하며 maze를 입력받는다.
• 동서남북을 dy, dx에 짝지어 저장한다.
• 최대값을 저장할 변수 INF을 sys.maxsize로 선언한다.
• 비용을 저장할 2차원 리스트 dist를 INF로 채워 선언한다.
• 0, 0은 출발지이므로 dist[0][0]을 0으로 갱신한다.
• 힙으로 사용할 q를 선언하고 (0, 0, 0)을 넣는다. (비용, y좌표, x좌표)
• q가 존재하는 동안 반복하는 while문을 돌린다.
  -> q에서 cost, y, x를 추출한다.
  -> 만약 cost가 dist[y][x]보다 클 경우, 다음 반복으로 넘어간다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny에 y+dy[i]를 저장한다.
  --> nx에 x+dx[i]를 저장한다.
  --> ny가 0 이상, m 미만이고, nx가 0 이상, n 미만일 경우,
  ---> 만약 maze[ny][nx]가 '1'일 경우, nxt_cost를 cost+1로 선언한다.
  ---> 그 외의 경우, nxt_cost를 cost로 선언한다.
  ---> 만약 dist[ny][nx]가 nxt_cost보다 클 경우,
  ----> dist[ny][nx]를 nxt_cost로 갱신한다.
  ----> q에 (nxt_cost, ny, nx)를 넣는다.
• dist[m-1][n-1]을 출력한다.

Code

import heapq
import sys
n, m=map(int, input().split())
maze=[]
for _ in range(m):
    maze.append(str(input()))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
INF=sys.maxsize
dist=[[INF]*n for _ in range(m)]
dist[0][0]=0
q=[]
heapq.heappush(q, (0, 0, 0))
while q:
    cost, y, x=heapq.heappop(q)
    if cost>dist[y][x]:
        continue
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<m and 0<=nx<n:
            if maze[ny][nx]=='1':
                nxt_cost=cost+1
            else:
                nxt_cost=cost
            if dist[ny][nx]>nxt_cost:
                dist[ny][nx]=nxt_cost
                heapq.heappush(q, (nxt_cost, ny, nx))
print(dist[m-1][n-1])