최단 경로가 판단 되는 부분

1)
우선 설명해주신 내용은 100% 맞습니다!

2)
공부 방법은 개인마다 취향이 있으니,
맞는 공부 방법을 찾아나가는 것이 좋습니다.
개인적으로는 유니티나 코딩 언어 문법처럼 '익숙해져야' 하는
과목들은 빠르게 훑어보고 나중에 돌아와서 필요할 때 찾아보는 것을 좋아합니다.
반대로 수학이나 알고리즘처럼 '깊이 생각해야' 하는 과목들은
느리더라도 한줄 한줄 따져보는게 중요하다고 생각합니다.

그리고 강의 진도는 온라인 강의 특성상 요약해서 빠르게 진행되지만,
저도 처음에 해당 내용을 익힐 때 몇 시간만에 익힌 것이 당연히 아닙니다.

알고리즘의 경우, IT 베스트셀러인 [프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 세트]에서
많은 영감을 받았는데 회사 다니면서 저녁마다 조금씩 학습하다보니
책 2권을 다 보는데 1년 넘게 걸렸습니다.
그리고 지금 하시는 것처럼 동일한 내용을 반복해서 학습하기도 했는데,
2~3번 보다 보면 이전에는 미처 생각하지 못했던 새로운 부분들이 보이기도 했습니다.

참고로 유니티 엔진은 API 외우는게 너무 지루해서 책은 도저히 볼 엄두가 안 나길래,
고민끝에 강제로 조금씩이라도 공부하게 주말마다 학원을 등록해서 다녔습니다.
유니티 관련 오프라인 학원만 4개를 다녀본 것 같은데
지금 생각하면 돈이 너무 아까울 정도로
대부분 퀄리티가 낮았던 기억이 있습니다.
그래도 저녁이나 주말마다 조금씩 뭐라도 꾸준히 공부를 하다보면,
그게 쌓이고 쌓여서 몇 년 정도 지나면 눈덩이처럼
지식이 급상승한 것이 체감되는 날이 오게 됩니다.

첫번째 루프에서는 방문하지 않았고, 거리가 int의 최댓값이 아니거나(최초 시작지점을 거르는 용도)
최단거리인 버텍스를 찾아냅니다. 여기가 바로 지금 방문 할 버텍스가 되는 것이죠

-> 이건 맞습니다.

저 if문의 비교는 단순히 distance[next]에 int의 최댓값이 들어가 있는 걸 활용한 비교인가요?

-> 이건 반은 맞는데, 항상 최대값을 고려해서 비교하는 것은 아닙니다.
다익스트라는 일반적인 DFS BFS와 다르게
모든 간선이 공평하지 않고 특정 수치(점수)를 갖게 됩니다. (ex. 거리)
따라서 가장 먼저 발견한 경로라고 해도,
뒤늦게 발견한 경로가 더 우수한 상황이 생길수도 있는데
그것을 위한 갱신이라고 보시면 됩니다.

이해를 돕기 위해 위 그림을 보시기 바랍니다.
0번 정점에서 시작을 한 상황인데,
1) 2번과 1번 정점을 발견합니다.
2) 그러나 2번 정점이 가장 가까우니 먼저 방문을 하게 됩니다.
3) 2번 정점을 방문하면서 3번 정점을 발견합니다 (거리는 1+1000 = 1001)
4) 3번과 1번 정점을 발견했는데 이 중 더 가까운 1번 정점을 방문합니다.
5) 1번을 방문하면서 발견은 했지만, 아직 방문하지 않은 3번에 대한 더 좋은 경로를 알게 됩니다
(1+1000 보다는 10+10이 훨씬 더 가성비가 좋기 때문)
6) 3번을 최종적으로 방문하지만, 기록상 0->2->3이 아닌 0->1->3을 통해서 방문한 것으로 기록

문의주신 if 비교 후 업데이트 하는 부분은 5)번 스텝에 해당한다고 보시면 됩니다.
물론, 최초 상태에선 intmax가 들어있으니 그것도 '더 좋은 경로'를 발견한 상태에 해당하긴 하지만,
그 다음에도 또 체크를 하는 이유는 언제든지 이전에 '발견'한 경로보다 더 좋은 경로를 발견할 수 있기 때문입니다.
이 알고리즘을 따르면, '방문'한 점은 무조건 최단거리라는 것을 수학적 귀류법으로 증명 가능합니다.
(= '방문'한 다음에 뒤늦게 더 좋은 경로를 찾을 수 없음)
(= '발견'만 하고 '방문'을 아직 하지 않은 상태에서는 뒤늦게 더 좋은 경로를 찾을 수 있음)

답변 정말 감사드려요!

특히 "그리고 지금 하시는 것처럼 동일한 내용을 반복해서 학습하기도 했는데,

2~3번 보다 보면 이전에는 미처 생각하지 못했던 새로운 부분들이 보이기도 했습니다."

이 부분 완전 공감갑니다

실은 이 부분 처음 들었을때는 그런가 보다 하고 넘어갔다가 다시 해보니까 의문이 들더라고요

빨리 복습을 끝내고 3번째 강의로 넘어가고 싶네요 ㅎㅎ

언제나 감사드립니다

위의 그래프를 기준으로 설명을 해보면,

첫번째 for루프에서 방문한적이 없고, 시작점에서 가장 가까운 지점은 시작점 0 정점밖에 없으니, closest == distance[0], now = 0이렇게 설정이 되겠죠. 첫번째 for를 지나서 이제 0을 방문하게 됩니다 (visited[0] = true;)

이제, 두번째 for루프를 통해서 0정점에 연결되어 있고, 방문한적이 없는 정점을 찾습니다. 1번과 2번 정점만이 두가지 조건을 통과 할 겁니다. 양쪽다 방문한 적이 없으니까 if(nextDist < distance[next])는 무조건 통과해서 distance[1] = 0 + 10, parent[1] = 0

distance[2] = 0 + 1, parent[2] = 0 이렇게 일단, 기록이 됩니다.

다시 while의 처음으로 돌아와서 closest와 now는 각각 최댓값과 -1로 초기화 되고 첫번째 for루프로 들어갑니다. 

첫번째 for루프에서는 2번점이 0에서 더 가까우니까 now = 2가 됩니다. 이번에는 2번을 방문하는게 되겠죠.(visited[now] = 2)

두번째 for 루프에서 이전과 마찬가지로 3번은 방문한적이 없기에 distance[3] = 1 + 1000, parent[3] = 2로 기록이 됩니다.

다시 while의 처음으로 돌아갑니다

 closest와 now는 초기화가 되고 첫번째 for 루프에서 1과 3중에서 현재 기록 된 거리가 더 가까운 1번 정점이 선택되겠죠 3번이 아니라 (1001 vs 1). visited[1] = true를 통해서 비로서 1번을 방문하게 됩니다.

두번재 for 루프에서 3번 정점이 2번 정점 방문시 발견되고 방문하진 않았으니까  3번 정점이 조건을 통과해서 거리 계산을 하는데, 일단 nextDist = 10 + 10이 되고 if(nextDist < distance[3])에서 보면 distance[3]은 이전 2번 정점 방문시 1001이라고 기록이 된 상태라서 이번에는 최댓값과의 비교가 아니라 20 vs 1001의 비교가 됩니다. 이때 1번을 통해서 3번으로 오는게 더 가까운게 되니까 3번 정점으로 오는 경로는 distance[3] = 20, parent[3] = 1로 갱신 됩니다.

이렇게 생각하면 맞나요?

답변 정말 감사드려요

하나 더 여쭤보고 싶은게 있는데

제가 일하면서 듣는거라 진도가 빠르진 않는데 매강 들을때마다 이전강에서 했던거 복습하는겸 코드 다시 보고 제가 다시 코드를 써봅니다. 덕분에 시간도 많이 걸리는데 이 방법 괜찮나요?

그리고 지금 처럼 일일이 한줄 한줄 다 따져보면서 공부를 하는데 시간이 좀 많이 걸려서 걱정인데 이렇게 하는게 좋은가요 아님 빨리 훑어보고 다시 처음부터 듣는게 좋을까요?