1. 우선순위 큐 사용하지 않은 코드 어떤 정점에서 뻗어나가는 여러 간선 중 가중치가 가장 작은것 하나만 선택하기 때문에 가중치가 같고 다른 정점을 향하는 두 개 이상의 간선에 대해서 모두 탐색하지 못해서 틀림.
2. 우선순위 큐 사용한 코드 위의 경우에서 가중치가 같자만 다른 정점 A, B를 향하는 간선들을 모두 탐색하지만, A에서 누적된 cumm(가중치 누적합)이 B에서도 그대로 누적되기 때문에 틀림. 다음 코드처럼 cumm을 없애고 아예 선택한 간선의 가중치를 갱신해주었더니 AC.
ssh9199 4년 전 2
1. 하나의 Node(정점)는 0개 이상의 다른 Node로 뻗어나가는 Edge(간선)를 가지고 있고, 그 Edge는 도착정점(index)과 해당 간선의 비용(cost)이라는 정보를 가지고 있도록 구조체를 구현했습니다.
2. 다익스트라 알고리즘을 수행하는 과정에서 계속 갱신해 줄, 시작점에서 i번째까지의 비용을 담은 answer 배열을, i가 시작점인 경우 0, 나머지를 INF로 초기화 해주었습니다.
3. index번째 Node와 지금까지 누적된 비용(cummCost)을 중심으로, index번째 정점이 가지고 있는 모든 간선을 탐색합니다. 이 때 각 간선을 e라 하면,
1) answer[e.next]를 e.cost + cummCost 와 비교하여 더 작은 값으로 갱신합니다.
2) 각 e 중 cost가 가장 작은 e를 선택합니다.
e의 next가 다음 index가 되며, cummCost도 e.cost만큼 누적해줍니다.
이 때 cost가 가장 작은 e가 없으면 코드의 minEdge.next == -1이 되어 while문을 빠져나갑니다.
우선순위 큐를 사용하지 않고 이런식으로 구현했습니다. 할 수 있는 한 여러 반례들을 찾아보고 입력해보아도 다 맞는 답이 나오던데, 어느 부분에서 틀린건지 감이 잡히지 않습니다. 도움 부탁 드립니다. 의미가 있을지는 모르겠지만 4%에서 "틀렸습니다" 처리 되었습니다.