[백준/16475] 수학 미로 (Python)

Problem : https://www.acmicpc.net/problem/16475

16475번: 수학 미로

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:17:27

 

---

 

문제 설명

 

 

성일이는 성동구에서 미로탈출을 제일 잘하는 사람이다. 자신의 실력을 검증해보고 싶었던 성일이는, 세상의 모든 어려운 미로를 정복하기 위해 여행을 떠났다. 세계 각국의 어렵다 하는 미로를 손쉽게 정복하던 성일이는, 어느 날 난관에 부딪혔다. 이전과 다른 특징의 미로에 성일이는 혼란스러운 나머지 기절해버렸다. 미로의 특징은 다음과 같았다.

 

• 총 N개의 지역이 M개의 길로 이어져 있고, M개의 길은 통행할 수 있는 방향이 하나로 정해져 있다.
• 각 지역의 번호는 1~N 사이의 정수이다.
• N개의 지역 중 K개의 지역에는 스위치가 있다. 스위치가 있는 지역에 방문할 때에는 스위치를 무조건 눌러야 한다. 이 지역들을 '함정 지역'이라고 부른다. M개의 길 중 L개의 길은 스위치를 P번 누를 때마다 방향이 거꾸로 변한다. 이 길들을 '함정 길'이라고 부른다. 스위치를 누른 횟수가 P번이 되면 함정 길들의 방향은 거꾸로 변하고, 스위치를 누른 횟수는 0으로 변한다. 

 

잠시 후 깨어난 성일이는, 너무 어려운 미로여서 우리에게 약간의 힌트를 얻고자 한다. 그가 필요로 하는 힌트는 출발지점에서 도착지까지 도달할 수 있는 가장 짧은 거리다. 성일이가 미로를 시작하는 출발점이 S, 도착점이 E라 할 때, 성일이가 미로를 탈출할 수 있도록 성일이가 원하는 힌트의 답을 알려주자.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 N, M, K, L, P, 값이 차례로 주어진다. (1 ≤ N, M ≤ 10,000, 0 ≤ K ≤ N, 0 ≤ L ≤ M, 1 ≤ P ≤ 10)

두 번째 줄에, K개의 함정지역의 번호가 주어진다.

세 번째 줄부터, M-L줄에 걸쳐, 일반 길의 정보가 A, B, C 값으로 주어진다. 이후 L줄에 걸쳐서, 함정 길의 정보가 A,B,C 값으로 주어진다. 이때 A지역에서 B지역으로 이어진 일방통행길 의 거리가 C이다. (0 < C ≤ 10,000)

마지막 줄에는 출발지 번호 S와 도착지 번호 E가 주어진다. 출발지점은 함정지역이 아니다.

 

출력

 

출발 지점에서 도착 지점으로 가는 최단경로를 출력한다.

경로가 없을 경우 -1을 출력한다.

 

입력 예시

 

6 9 1 1 2
2
1 2 1
2 1 1
1 6 1
1 5 5
2 5 2
5 3 6
5 4 2
4 3 2
3 6 1
1 3

 

출력 예시

 

6

 

 

---

 

풀이

 

다익스트라로 해결해 보자. 총 스위치 상태는 P*2가지가 존재하므로 (P*2, N)만큼의 dist 배열을 관리하도록 하자. P <= x < P*2일때는 스위치가 눌려 함정 길이 뒤집힌 경우, 그렇지 않으면 뒤집히지 않은 경우로 볼 수 있다. 

 

풀이 코드

from heapq import *
from collections import defaultdict
import sys
input = sys.stdin.readline
MAX = float('inf')

N, M, K, L, P = map(int, input().split())
switch = set(map(int, input().split()))
edge_dict = defaultdict(list)
trap_edge_dict = [ defaultdict(list) for _ in range(2) ]

for i in range(M) :
  a, b, c = map(int, input().split())
  if i >= M-L :
    trap_edge_dict[0][a].append((b, c))
    trap_edge_dict[1][b].append((a, c))
  else :
    edge_dict[a].append((b, c))
S, E = map(int, input().split())

dist = [[MAX]*(N+1) for _ in range(P*2)]
q = [(0, S, 0)]
dist[0][S] = 0
flg = False

while q :
  d, node, tag = heappop(q)
  if node == E :
    flg = True
    break
  for nxt, cost in edge_dict[node] :
    nxt_tag = (tag + 1) % (P*2) if nxt in switch else tag
    if dist[nxt_tag][nxt] > d + cost :
      dist[nxt_tag][nxt] = d + cost
      heappush(q, (d + cost, nxt, nxt_tag))

  for nxt, cost in trap_edge_dict[tag // P][node] :
    nxt_tag = (tag + 1) % (P*2) if nxt in switch else tag
    if dist[nxt_tag][nxt] > d + cost :
      dist[nxt_tag][nxt] = d + cost
      heappush(q, (d + cost, nxt, nxt_tag))

print(d if flg else -1)

풀이 완료!