# 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억이 된다! ![](/files/-MiLjqqc097SESDl9wCv) ⭐️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 : ❌ --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-4/4..md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.