[BOJ]18223번: 민준이와 마산 그리고 건우

 

www.acmicpc.net/problem/18223

---

다익스트라 응용 문제입니다.

 

최단 경로 내에 특정 경로가 포함되어 있다면 TRUE, 아니면 FALSE 입니다.

 

이런 경우에는 before[targetNode]라는 리스트를 만들어서

targetNode 이전에 어디를 방문했었는지 저장해놓습니다.

 

단, 어떤 노드를 새로 방문을 했을 때 목적지로부터 거리가 갱신되는 경우는 두 가지인데요.

1) 목적지로부터 거리가짧아지는 경우

2) 목적지로부터 거리가 이전과 같은 경우

 

이렇게 두 가지가 있습니다. 

일반 다익스트라면 1번만 저장하면 되지만 지금은 2번도 경우의 수로 따져줘야 합니다.

 

그러므로 1번의 경우에는 이전에 저장한 before[targetNode]를 전부 지워버리고 새로 시작하고

2번의 경우에는 before[targetNode].add(newNode) 이런식으로 이 노드도 갈 수 있음을 표시해줍니다.

 

 

이렇게 다익스트라를 돌려 표시를 해주고 난 뒤

목적지 노드로 부터 before[] 리스트를 사용해서 bfs를 돌리면 됩니다.

이 bfs는 목적지 => 출발지로 가는 bfs인데

bfs를 돌면서 방문한 노드 중 건우가 있는 노드가 있다면 TRUE, 없으면 FALSE가 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ18223.java