[파이썬] 백준 16475 : 수학 미로 (골드1)

[파이썬] 백준 16475 : 수학 미로 (골드1)

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

---

풀이

방향성 생각

• 2021 카카오 채용연계형 인턴십랑 비슷한 문제
  위 문제는 비트마스킹으로 변하는 간선을 관리했다면, 현재 문제는 단순 cycle을 통해서 문제 풀이.
• 정방향 간선이랑 역방향 간선이 들어오는데, 정방향은 항상 탐색할 수 있고, 역방향인 경우 간선이 뒤집혔는지 유무에 따라서 체크해야한다.
  • 역방향 간선은 상태를 체크할 수 있는 변수를 추가해서 정방향 / 역방향으로 모두 넣어준다.

 

---

전체코드

import sys
import heapq as hq

input = lambda : sys.stdin.readline().strip()
INF = float('inf')

N,M,K,L,P = map(int,input().split())
trap_nodes = set(map(int,input().split()))

# 간선 입력받기 : 일반 간선은 0 / 정방향 간선은 1 / 역방향 간선은 -1로 tag를 남겨준다.
G = [[] for _ in range(N+1)]
for i in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost,0))
    if i>=M-L:
        G[a].append((b,cost,1))
        G[b].append((a,cost,-1))

sx,ex = map(int,input().split())

# 스위치를 총 2P번 누르면 초기 상태로 되돌아오므로 cycle = 2P
cycle = 2*P
find = False

# V[뒤집힌 상태 0/1][누적 스위치 횟수 % P][node]
V = [[[INF]*(N+1) for _ in range(P)] for _ in range(2)]
V[0][0][sx] = 0
heap = [(0,sx,0)]
while heap:

    t,x,c = hq.heappop(heap)

    if x == ex:
        find = True
        break

    for nx,cost,is_trap_edge in G[x]:
        nt = t+cost
        # 다음 노드가 trap node이면 스위치 횟수 늘려주기.
        nc = c + (nx in trap_nodes)
        # 현재 횟수 c를 통해서 간선이 뒤집혔는지 유무를 rev에 저장장
        rev = (c%cycle) >= P

        # 탐색하기: 횟수는 항상 P로 나눠주기기
        if ((not is_trap_edge) or (is_trap_edge==1 and not rev) or (is_trap_edge==-1 and rev)) \
            and nt < V[rev][nc%P][nx]:
            hq.heappush(heap,(nt,nx,nc))
            V[rev][nc%P][nx] = nt

print(t if find else -1)

코멘트

• c%cycle여기서 nc로 써서 틀림...
• 현재 상태값을 사용하는지, 다음 상태값을 사용하는지 꼼꼼하게 체크하기.