일단 dijkstra는 크게 2가지로 나눌 수 있습니다.

1. 새로 알게된 길 중에서 최솟값을 찾기.

이게 26번째에서 31번째로 추정이 됩니다.

2. 기존 거리보다, 새로 알려진 길이 더 작다면, 최단 거리 업데이트

32번째 줄인 v가, 새로 추가된 정점입니다. 

문제는, 26번째 줄에서, 31번째 줄에서 for문이 다 돌고도

v가 업데이트가 되지 않은 경우인데요. 데이터를 바꿔볼게요.

5

3

1 2 2

1 3 5

2 3 1

1 3

이런 데이터가 있습니다. 다익스트라 알고리즘을 아신다는 가정하에 중간과정 생략하고 답변을 작성하겠습니다.

v=2일 때,

[0, 1, 2, 3, inf, inf] 이래 업뎃 되는군요.

다음에, 3을 방문했을 때에는, 1과 2는 방문한 정점이고 4, 5는 inf군요~

그냥 업데이트를 안 합니다. 여기서 끝내면 좋으련만.

for문 코드에 의해서 몇 번 더 돌겠지요.

이 경우, v=0이기 때문에, 이미 있지도 않은 점을 방문했다~ 이렇게 되는 겁니다.

심지어, dist[0] = 0이라고 하지 않으셨나요?

그리고 g[0][x] = 0이네요? (x = 도시들 집합에 속해있는 정점)

이 과정에서, dist[2] > dist[0] + g[0][2]이기 때문에

dist[2]가 0으로 업데이트 되는 것이고요.

그러면 시작점인 1로 초기화한 경우에는 어떻게 될까요?

v=3일 때

[0, 1, 2, 3, inf, inf] 이렇게 되었지요?

26번째 줄에서 31번째 줄을 봅시다.

if문에 걸리는 조건이 없기 때문에, v가 업데이트가 당연히 안 될 겁니다.

그 경우, v=1이 됩니다.

자. 그 다음에..

dist[t] > dist[1] + dist[1][t] 인가? 36번째 줄을 주목할 필요가 있습니다.

즉, 이미 알려진 경로보다, 1을 거쳐서 가는 것이 더 빠른가?

이 조건에 걸리는가? 를 생각하실 필요가 있는데요.

이미 우리는 1을 거쳐서 가는 경우, 다 탐색했습니다.

출발점을 거쳐가서 도착점에 도착하는 경우, 이미 다 계산을 했으니까요.

그렇기 때문에 update가 되지 않는 것이지요. 그렇기 때문에, 2글자 차이로 맞는 답이 나오는 것이지요.

ps.

priority Queue. (Max heap, Min heap)에 대해서 공부를 하시면 좋습니다.

다익스트라 알고리즘을 조금 생각해 보시면 어떻게 적용하셔야 할 지는 금방 아실 듯 싶습니다~

답변해 주신 부분은 이해가 갑니다.

그런데 v를 선언만하고 초기화 하지 않았는데도 맞았습니다. 그렇다면 결국에는 반드시 한번은 들어간다는 뜻이 되잖아요?

그런데 제 생각에는

  for (f = 1; f <= N; f++)    if (!c[f] && dist[f] < min)    {     min = dist[f];     v = f;    }

이 부분에서 if문 조건을 만족하지 않는 경우는 있다고 생각하거든요. 그런데도 답이 맞은 걸로 봐서는 어떤 경우던지 한번은 들어갔다는 말이 되는데 이해가 가지 않습니다. ㅠㅠ

테스트케이스는 반드시 if문을 들어가는 상황만 있나봐요.

제시해주신

5

3

1 2 2

1 3 5

2 3 1

1 3

에서 도착점을 5로 하면 v를 초기화하지 않으면 역시 에러가 났어요!!!!

그래서 제가 생각했을 때는 v 값을 S로 선언해주면 좋겠다고 생각하는데 괜찮을까요??

테스트 결과 답이 맞으면 맞은 것이지요.

coco님 코드에서는, v = 0이 되는 경우만 조심하시면 됩니다.

아니면, dist[0]을 inf로 초기화하는 방법도 있고요. 연습장에 루프가 어떻게 돌아가는지

조금만 그려보셔도 아실 듯 싶습니다~

ps.

v 값은 왠만하면 초기화를 시켜주시는 게 좋습니다.

초기화를 안 시켜주는 경우, 어느 값이 들어갈 지 모르기 때문입니다.

감사합니다. ㅎㅎ