다익스트라를 제대로 구현하셨다면 틀릴 이유가 없는데.. 흐음..

어떻게 간선을 구축하셨고, 어떤 식으로 처리하셨는지 간단하게 설명 부탁드려요..

처음에는 저도 이런 걸 잘 못했는데.. 연습이 무쟈게 필요하더라고요.

1. 정점과 가중치, 간선 구축
우선 tree라는 클래스를 만들어서 이곳에 어느 정점로 향했는지(toNum)와 가중치(weight)를 LinkedList 형태로 저장하게 하였습니다. 그리고 tree 형태의 배열을 정점의 갯수만큼 만들어서 i번째 배열에 가중치값이 얼마이고 어느 정점으로 향한 것인지 데이터를 계속 저장하였습니다. [tree[A].toNum = B 이고 tree[A].weight = C 이면 A+1에서 B로 향한 간선이 있고 가중치값은 C이다. 라는 뜻이 됩니다. 간선구축은 이렇게 하였습니다.]

2. 가중치 최소값 저장할 배열 구축
그 다음 정점의 갯수만큼의 1차원 배열을 만들었습니다. 여기에 시작점의 정점에서 각 정점으로의 최소값을 저장하려고 만들었는데 시작점 자신은 -0으로 저장하고 그 이외는 모두 -1로 저장하였습니다. 주어진 가중치값은 10이하의 자연수니까 음수가 나올리가 없을꺼고 그래서 -1으로 해둔다음 이 정점을 지났는지 여부를 확인하는데 사용할 수 있기 때문이죠.

3. DFS 알고리즘을 활용한 가중치 최소값 저장
그다음 DFS알고리즘을 활용하여 stack을 만들고, 시작점(startN)을 먼저 넣어준다음 stack이 비어질때까지 while문을 만들었습니다. while문의 내용은 다음과 같습니다
1. stack에서 한 개의 값을 pop 받는다. (temp에 저장)
2. 정점을 지났다면 continue, 아니면 정점을 지났다고 표시한다(check[temp-1] = true)
3. 받은값(=현재 정점까지의 가중치값)에서 이어진 정점까지의 가중치값을 더하는데 이 값이 이어진 정점의 현재 최소값이 -1이면(아무 값도 입력이 안된것이니) 바로 저장하고, 그렇지 않으면(다른 경로를 톻한 가중치 값이 저장이 되어있다는 것이니) 더한 가중치 값이랑 이 값을 비교하여 최소값을 배열에 저장합니다
4. 그리고 이어진 정점값을 stack에 넣어줍니다.
5. stack이 비어질때까지 1번으로 되돌아가기.

4. 가중치최소값 배열을 기반으로 정답출력
이런 과정이면 각 정점까지의 최소값을 저장해둔 1차원 배열에 원하는 정보가 저장될 것이라 생각하여 이 값들을 모두 출력합니다. ( 만약 1차원 배열의 원소값 중 아직도 -1인게 있다면 이곳은 경로가 존재하지 않는 경우일태니 iNF를 출력합니다 )

쓰다보니 간단하지 않게 되었지만 이렇게 하였습니다..!

아래 TC에서 답이 다르게 나오네요.

그 이유는 stack에 넣지 않는 조건이 잘못되었기 때문입니다. stack에서 뺀 순간. 도착점에 방문했다고 표시하는데요.

그러면서, aaa까지 가는 최단 cost를 갱신하지 않죠.

stack에 cost 순으로 저장되어 있지 않은 한 (cost가 낮은 순이 우선순위가 높음.)

시작점에서 aaa까지 가는 최단 cost가 스택에 먼저 뺀 순이다. 라는 보장이 있나요?

위 케이스에 대해서 답이 어떻게 나와야 하나요?