백준 1261 파이썬: 알고스팟

문제의 근원

• https://www.acmicpc.net/problem/1261

알고리즘 분류

• 차트 탐색
• 다익스트라
• 0-1 너비 우선 탐색

설명

다음 블록이 0인 경우 대기열의 시작 부분에 해당 위치를 배치하여 우선순위를 처리한다는 점에서 일반 대기열을 사용하여 BFS로 해결할 수 있습니다.

이 문제에서와 같이 그래프에서 0과 1의 가중치로 나타낼 수 있는 경로를 찾기 위해 사용하는 너비 우선 탐색을 0-1 너비 우선 탐색이라고 합니다.

암호

import sys
from collections import deque

input=sys.stdin.readline
M,N=map(int,input().split())
mage=()
for i in range(N):
    mage.append(input().strip())

visit=((-1 for _ in range(M)) for _ in range(N))
visit(0)(0)=0
queue=deque()
queue.append((0,0))
da=(0,1,0,-1)
db=(1,0,-1,0)
while queue:
    a,b=queue.popleft()
    for i in range(4):
        na=a+da(i)
        nb=b+db(i)
        if na<0 or nb<0 or na>=N or nb>=M or visit(na)(nb)!=-1:
            continue
        else:
            if mage(na)(nb)=='1':
                queue.append((na,nb))
                visit(na)(nb)=visit(a)(b)+1
            else:
                queue.appendleft((na, nb))#일반적인 큐를 이용한 BFS와는 다른 점 : 벽을 부수지 않고 이동하기 때문에 우선적으로 이길을 선택해서 경로를 선택하면 되기 때문에 큐의 맨 앞에 넣어준다.
                visit(na)(nb)=visit(a)(b)
print(visit(N-1)(M-1))