BOJ 14497 주난의 난(難)(Python 3)

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

 

 

숨바꼭질3과 비슷한 문제이다.

 

주난이 상하좌우로 이동할 수 있다고 가정할 때, 친구가 있는 곳으로 이동하는데 1초가 걸리고, 빈 공간이 있는 곳으로 이동하는데 0초가 걸린다고 생각하면 된다.

 

빈 공간으로 이동할 때는 appendleft로 큐의 맨 왼쪽에 넣어주고, 친구가 있는 곳으로 이동할 때는 append를 이용해 큐의 오른쪽에 넣어준다.

 

숨바꼭질3을 푸는 방법처럼 heapq를 이용해서 풀어도 풀 수 있다.

 

 

from collections import deque
n,m=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
D=[list(map(str,[*input()])) for _ in range(n)]
S=[[-1]*m for _ in range(n)]
q=deque()
q.append((x1-1,y1-1))
S[x1-1][y1-1]=0
dx,dy=[0,0,1,-1],[1,-1,0,0]
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 S[nx][ny]==-1:
            if D[nx][ny]=='0':
                q.appendleft((nx,ny))
                S[nx][ny]=S[x][y]
            else:
                q.append((nx,ny))
                S[nx][ny]=S[x][y]+1
print(S[x2-1][y2-1])