> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-4/4..md). # 4. 합승 택시 요금 올것이 왔다\~ 최단거리(최소비용) 구하는 플로이드 와샬 알고리즘 시작점 - 경유지 - 도착점 시작점, 경유지, 도착점 모두 n개의 정점에 대해 다 해보는 완전 탐색 문제이다.\ 즉, 3중 반복문으로 구현한다. n 제한은 최대 200이기 때문에 200\*200\*200 = 8백만 << 1억으로, 시간 복잡도 결과는 1초 이내라고 할 수 있다. 배운점 1. 3중 반복문은 반복문은 최대한 깊이를 줄이는 것이 좋다는 이념에 따라 안 좋은 것이라고(?) 생각했는데, 이러한 문제를 풀 때는 적절히 사용할 줄 알아야하는 것을 배웠다. 2. 말로만 듣던 플로이드 와샬 알고리즘을 처음 접해봤다. 문제 풀이 영상의 제작자님께서 설명을 잘해주셔서 어렵지 않게 이해할 수 있었다. 플로이드 와샬 알고리즘을 이용한 다른 문제들도 풀어봐야겠다. 혼자서 풀 수 있을지 모르겠지만..? 틀린 이유\ 정답은 거리값 3개를 더하는 것(D\[start]\[end] = D\[start]\[k]+D\[k]\[end])이기 때문에 처음에 Dist 배열 값을 Integer 최댓값으로 저장해버리면 3개 값을 다 더했을 땐 오류가 난다. 그렇기 때문에 fare의 최댓값에 따른 최댓값으로 INF를 설정해줘야한다. 문제에서 fare의 최댓값은 10만이라 3개의 거리값을 다 더했을 때에도 최댓값은 30만일 것 같았는데, 해설 영상에서는 넉넉히 40만을 잡아주었지만.\ 근데 40만 하면 틀리고, 40만->80만 : 3/5 틀린 테케 해결, 80만->1억 : 모든 테케 통과&정답 왜지?🧐 start->k->end 바로 이렇게 가는 것이 아니라\ start->a->b->c->d->...->end 이렇게 되는 경우가 있기 때문이다!(중간에 경유하는 정점의 갯수는 출발지와 도착지를 제외한 N-2)\ 정점의 갯수N은 최대 200, N-2 = 198. (200이라고 잡고) 모든 노드를 다 거쳤을 때가 최단거리라고 한다면 모든 간선의 갯수는 N\*(N-1)/2 = 200\*199/2 = 19900이고, fare의 최댓값은 10만이기 때문에 19900\*100000 = 약 2만 \* 10만 = 20 0000 0000 = 최대 2억이 된다! ![](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MiL3bcKcyU73oF_f6Gi%2F-MiLjqqc097SESDl9wCv%2FScreen%20Shot%202021-08-30%20at%208.08.20%20PM.png?alt=media\&token=20cd282f-adf2-4eaf-ab11-5ee4b0630fbb) ⭐️3중 for문으로 **최대 N-2개의 경유지를 거쳐** **\[모든 정점 - k - 모든 정점]**의 **최단거리**를 구할 수 있는 이유 ex) Dist\[0]\[0] = 0, Dist\[0]\[3] = 1, Dist\[3]\[4] = 1, Dist\[4]\[0] = 1, 따라서 Dist\[0]\[0] = 1\ 0->3->4->0 의 최단거리 판단 순서\ ① 0->3->4 : start = 0,k=3, end = 4. D\[0]\[4] = 0 , D\[0]\[3] + D\[3]\[4] = 1.\ 최단 거리에서는 D\[0]\[4] = ∞ > D\[0]\[3] + D\[3]\[4] ∴D\[0]\[4] = D\[0]\[3] + D\[3]\[4]\ ② 0->4를 구했으니, 4->0도 구할 수 있다.\ Dist\[4]\[0] = 1 이기 때문에, 결론적으로 Dist\[0]\[4] == 1 && Dist\[4]\[0] == 1을 만족하여 Dist\[0]\[0] = 1이 된다. 3중 for문 순서 왜 k가 가장 밖에 있어야하는가? 가장 안쪽에 있으면 틀리는 이유 ex) 1->3->2->4 최단 거리를 구할 때, 위에서 구한 것과 마찬가지로 올바른 실행 순서 : \ ① 1->3->2\ ② 1->2->4\ \ 틀린 실행 순서 i->j->k (k가 가장 안쪽에 있을 경우)\ 1->3->2 와 1->2->4\ 👉🏻1->3->2 : i=1,j=2,k=3. 1->2->4 : i=1,j=4,k=2 이다. 반복문의 순서에 따라 1->2->4가 먼저 구해진다. 하지만 1->3->2를 먼저 구하지 않는 이상, 1->2는 여전히 경로가 존재하지 않기 때문에 1->2->4 또한 경로는 존재하지 않게 되고, 1->3->2에서도 1->3 : 존재, 3->2 : 존재, 1->3->2 = 1->2로써 존재하지만, 1->2->4를 구하지 못했기 때문에 결과적으로 최단 경로를 구할 수 없게 된다.\ 따라서 1->3->2가 먼저 실행되야하기 때문에 i,j,k 순서가 아니라 k,i,j 순서가 되야한다.\ k,i,j 순서가 되면 1(i)->3(k)->2(j)를 실행하고 난 후, 1(i)->2(k)->4(j)를 실행할 수 있다!?\ 3->2->4 : start=3,end=4, k=2\ 1->3->4 : start=1,end=4,k=3 i,j의 실행 순서 : 1->2, 1->4 순서로 하기 때문에 i가 상위, j가 하위에 있는 것은 알겠다.\ 1\. k - (i - j)\ 2\. (i - k - j)\ 3\. (i - j) - k : ❌