[백준 12930번] 두 가중치 (Python3)

from heapq import *

def dij():
  DP = [{} for i in range(N)]
  hq = [(0,0,0,1)]
  while hq:
    w1,w2,now,bit = heappop(hq)
    if w2!=0 and DP[now][w2]<w1:
      continue
    for next in range(N):
      if bit&(1<<next):
        continue
      bit1 = bit|(1<<next)
      w3,w4 = w1+graph[0][now][next],w2+graph[1][now][next]
      if DP[next].get(w4,1e9)>w3:
        DP[next][w4] = w3
        heappush(hq,(w3,w4,next,bit1))
  return min(w2*DP[1][w2] for w2 in DP[1]) if DP[1] else -1

N = int(input())
graph = [[[*map(lambda x:1e9 if x=="." else int(x),input())] for i in range(N)] for i in range(2)]
print(dij())

비트마스킹 + 2차원 DP 다익스트라로 해결하였다.

KCM travel [백준 10217번] KCM Travel (Python3) (tistory.com) 문제와 비슷하게 w2에 대한 w1의 최솟값을 구하는 2차원 DP를 만들어서 해결하였다.

 

풀이를 설명하면,

1. w1에 대한 그래프와 w2에 대한 그래프를 입력받는다.

2. 다 익스트라를 실행하여 next 노드로의 두번째 가중치가 w2일 때 w1의 최솟값을 구한다.

3. 이때 비트마스킹을 통해 사이클이 생기지 않도록 한다.

 

3에서 비트마스킹을 해주지 않았더니 노드들이 무한루프를 그리는 결과를 가져왔다. 어차피 N은 충분히 작고, 사이클을 포함한 경로가 최단거리일 가능성은 전혀 없기 때문에 비트마스킹을 사용하여 해결하였다.

 

여담) 내 코드가 이 문제의 숏코딩 순위 1위, 파이썬 기준 성능 1위가 되었다.