궤도

문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행해 1->B, 1->C의 최단 거리를 알아야 하고 B에 대하여 실행해 B->C, B->N의 최단 거리를 알아야 하고 C에 대하여 실행해 C->B, C->N의 최단 거리를 알아야 한다. N까지 가는 두가지 경로 중 작은 것을 택하면 된다. 다익스트라 알고리즘의 자세한 구현 설명은 myunji.tistory.com/344 [백준] 1753번 : 최단경로 문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없..