sarah950716   4년 전

어떤 경우에서 틀리는지 까지 발견했지만, 어떻게 고쳐야 할 지를 모르겠습니다.

풀이 방법은 다익스트라를 통해 최단거리를 구하고, 해당 경로에 속한 간선들을 모두 지워주고 최단경로가 달라질 때까지 계속 다익스트라를 돌리는 방식입니다.

그런데 입력이 아래와 같은 경우,

0 -> 1 -> 2 로 가는 경로와 0 -> 1 -> 3 -> 2 로 가는 경로의 길이가 3으로 같아, 0 -> 1, 1 -> 2, 1 -> 3, 3 -> 2 총 4개의 간선을 지워줘야 하는데, 다익스트라를 실행한 후 경로에 속한 간선을 모두 지우고 나면 두 경로 모두의 간선을 지우는 것이 불가능해집니다.

이와 같은 문제를 어떻게 해결할 수 있을까요?ㅠㅠ

4 5

0 2

0 1 1

0 3 5

1 2 2

1 3 1

3 2 1


iljimae   4년 전

안녕하세요. 저도 이 문제에 대해서 고민하다가 sarah950716님의 질문을 보고 왜 틀렸는지 알아차린뒤 겨우 해결했습니다. 

언급하신 테스트 케이스에서 두 경로를 모두 지우기 위해서는 도착점과 바로 연결되어 있는 노드들의 목록 (adj라고 부르겠습니다) 을 저장해두고, 다익스트라를 한번 돌립니다.  

d[x] = 노드 x까지 가는 최단거리라고할때, adj에 있는 노드중 d[adj[i]]+cost(adj[i],목적지) = d[목적지]를 만족하는 adj[i] 와 연결된 경로를 전부 지워줍니다. 그리고 나서 다익스트라를 한번 더 돌리면 답을 구하실 수 있을거에요. 

댓글을 작성하려면 로그인해야 합니다.