BOJ 9505 엔터프라이즈호 탈출(Python 3)

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

일반 BFS로 풀면 python, pypy로는 시간 초과가 나오는 문제이다.

그래서 heapq를 이용한 다이젝스트라로 문제를 풀었다.

그동안 다익스트라로 풀어야할 문제를 전부 bfs, deque로 풀어내서(...) heapq를 이용해 직접 풀은 문제는 이번이 처음이다.

저번에 숨바꼭질 질문 글을 통해 heapq의 존재를 처음 알게 되었는데 자주 써먹을 수 있을 것 같다.

다이젝스트라는 BFS와 상당히 유사하지만, BFS와의 차이점은 heapq를 이용하기 때문에 q에서 뱉어내는 좌표중에서 가장자리 좌표를 제일 먼저 뱉어내는 값이 최소값이라는 것이다.

K는 dict,defaultdict,list 셋중에서 뭘 하든 상관 없어 보인다. 아래 코드는 list를 이용해 만들었다.

코드 확인

from heapq import *
input=__import__('sys').stdin.readline
dx,dy=[0,0,1,-1],[1,-1,0,0]
Max=float('INF')
for __ in range(int(input())):
    k,m,n=map(int,input().split())
    K=[0]*26
    q=[]
    T=Max
    for i in range(k):
        a,b=map(str,input().split())
        K[ord(a)-65]=int(b)
    D=[input().rstrip() for _ in range(n)]
    S=[[Max]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if D[i][j]=='E':
                heappush(q,(0,i,j))
                S[i][j]=0
    while q:
        z,x,y=heappop(q)
        if x in [0,n-1] or y in [0,m-1]:
            print(S[x][y])
            break
        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]>S[x][y]+K[ord(D[nx][ny])-65]:
                S[nx][ny]=S[x][y]+K[ord(D[nx][ny])-65]
                heappush(q,(S[nx][ny],nx,ny))