4. 합승 택시 요금
올것이 왔다~
Last updated
올것이 왔다~
Last updated
최단거리(최소비용) 구하는 플로이드 와샬 알고리즘
시작점 - 경유지 - 도착점
시작점, 경유지, 도착점 모두 n개의 정점에 대해 다 해보는 완전 탐색 문제이다. 즉, 3중 반복문으로 구현한다. n 제한은 최대 200이기 때문에 200*200*200 = 8백만 << 1억으로, 시간 복잡도 결과는 1초 이내라고 할 수 있다.
배운점
3중 반복문은 반복문은 최대한 깊이를 줄이는 것이 좋다는 이념에 따라 안 좋은 것이라고(?) 생각했는데, 이러한 문제를 풀 때는 적절히 사용할 줄 알아야하는 것을 배웠다.
말로만 듣던 플로이드 와샬 알고리즘을 처음 접해봤다. 문제 풀이 영상의 제작자님께서 설명을 잘해주셔서 어렵지 않게 이해할 수 있었다. 플로이드 와샬 알고리즘을 이용한 다른 문제들도 풀어봐야겠다. 혼자서 풀 수 있을지 모르겠지만..?
틀린 이유 정답은 거리값 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억이 된다!
⭐️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 : ❌