> 문제 <

출처 : https://www.acmicpc.net/problem/1261

> 관련 알고리즘 <

다익스트라 알고리즘
== 최단경로 탐색 알고리즘
https://m.blog.naver.com/ndb796/221234424646 참고!

> 코드 <

1. 초안

def bfs(x,y,n,m):
  delx = [0,0,-1,1]
  dely = [-1,1,0,0]
  count=0
  while (x,y != n-1, m-1):
    room[x][y] = 'True'  # 방문표시
    for i in range(4):
        nx = x + delx[i]
        ny = y + dely[i]
        if nx==n-1 and ny==m-1:
            return count
    nx=0 
    ny=0
    for i in range(4):
        nx = x + delx[i]
        ny = y + dely[i]
        if (0 <= nx < n and 0 <= ny < m):
          if room[nx][ny]==0:
            x, y = nx, ny
            break
          elif room[nx][ny]==1:
                count+=1
                room[nx][ny]=0
                x,y=nx,ny
                break
          elif room[nx][ny]=='True':
              continue

  return count

n,m=map(int, input().split())
room=[]
for i in range(n):
  room.append(list(map(int, input())))

print(bfs(0,0,n,m))

from collections import deque
q=deque()

def bfs():
  delx = [0,0,-1,1]
  dely = [-1,1,0,0]
  while q:
    x,y = q.popleft() 
    for i in range(4):
      nx = x + delx[i]
      ny = y + dely[i]
      
      if 0<=nx<n and 0<=ny<m:
        if dist[nx][ny] == -1:
          if room[nx][ny] == 0:
            dist[nx][ny] = dist[x][y]
            q.appendleft([nx,ny])  # 0이 있는곳이 우선순위
          elif room[nx][ny] == 1:
            dist[nx][ny] = dist[x][y] + 1
            q.append([nx,ny])    


m,n=map(int, input().split())
room=[]
dist=[[-1]*m for i in range(n)]
for i in range(n):
  room.append(list(map(int, input())))
q.append([0,0])
dist[0][0] = 0
bfs()
print(dist[n-1][m-1])

> 다른코드 <

heapq 이용
https://home-body.tistory.com/446