[BOJ]12908번: 텔레포트 3

www.acmicpc.net/problem/12908

---

저는 다익스트라로 해결했습니다.

출발점, 도착점, 텔레포트 가능경로 6개 이렇게 총 8개의 노드가 존재하는 그래프로 변환하였습니다.

 

기본적으로 노드와 노드간의 거리는 abs(y1-y2) + abs(x1-x2) 입니다.

다만, 텔레포트 가능경로끼리의 거리는 10으로 고정됩니다.

이렇게 8개의 노드끼리의 경로를 셋팅해놓고

다익스트라를 돌려서 다익스트라(출발점, 도착점)을 구하면 그게 최단 경로가 됩니다.

---

코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ12908.py