백준 11657: 타임머신 (Swift)

시작점으로부터 모든 지점까지의 "최단거리"를 구해야하는 "다익스트라" !!!    가 아닌

"벨만-포드" 알고리즘을 사용하는 기본 문제입니다...

그 이유는 간선에 "음수"가 포함되어있기 때문인데요,

 

코테에 나오는 알고리즘을 암기하면서 벨만포드는 참 외우기 어려웠습니다.. ( 이유는 잘 모르겠네요.. )

 

- 자세히 보면 INF를 이용해 1차원 distance배열을 두고 시작하는 것,

- 함수의 첫 줄에서 시작점의 distance[start] = 0으로 초기화하는 것

이 두가지는 다익스트라를 구현할 때와 완전히 똑같습니다! 

 

한가지 큰 차이점은  

 

-다익스트라는  보통  "인접 리스트"에 각 node에서 갈 수 있는 node번호를 모아놓는 , "그래프"가 주인공인 알고리즘 이라면,

 

- 벨만-포드는 아래 코드의 7번 줄과 같이 edges를 모두 한 곳에 담아놓고 진행하는, "간선"이 주인공인 알고리즘 입니다!!

 

(라고 저는 외웠습니다... )

 

알고리즘 구현 암기라는 것이 원리를 이해하고, 중요한 point를 부분부분 기억해두면  손이 알아서 써내려가주기 때문에,

저는 위의 포인트를 중심으로 암기를 했습니다 ^^