[프로그래머스] 합승 택시 요금

[프로그래머스] 합승 택시 요금

노드 사이 가중치가 다르다는 점과 최저 택시요금을 구해야 한다는 점에서 다익스트라나 플로이드-와샬을 사용하면 되지 않을까 싶었습니다. 다익스트라보다는 플로이드-와샬이 이해도 더 잘 가고 재미있는 것 같아서 플로이드-와샬을 사용해서 풀었습니다.

풀이 방법

전체적인 틀은 플로이드-와샬 기본 코드를 사용해서 풀었습니다. 백터 전체를 INF로 초기화 한 뒤에 행과 열이 같은 인덱스일 때 0으로 채워줍니다. vector가 2차원이기 때문에 [i][0]은 시작 노드, [i][1]은 도착 노드, [i][2]는 가중치가 됩니다. dist 배열에 아래와 같이 가중치를 대입합니다. 플로이드-와샬 방법을 이용해서 1~n까지 노드 사이의 최단거리를 구합니다. 최종적으로 브루트포스 방식으로 answer를 구합니다. dist[s][i] + dist[i][a] + dist[i][b]에서 i는 거쳐가는 노드를 의미하며 s->i->a로 갈 때 s->i->b로 갈 때 최단거리를 더한 값을 구해줍니다.

#include #include #include using namespace std; int INF = 10000000; void floyd(vector>& dist, int n){ for (int k = 1; k <= n; k++) { //k : 거쳐가는 지점 for (int i = 1; i <= n; i++) { //i : 처음 지점 for (int j = 1; j <= n; j++) { // j : 도착 지점 if (i == j || i == k || k == j) continue; if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } } int solution(int n, int s, int a, int b, vector> fares) { int answer = 0; vector> dist(n+1, vector(n+1, INF)); for (int i = 1; i <= n; i++) dist[i][i] = 0; for (int i = 0; i < fares.size(); i++) { int start = fares[i][0]; int end = fares[i][1]; int weight = fares[i][2]; dist[start][end] = weight; dist[end][start] = weight; } floyd(dist, n); answer = dist[s][a] + dist[s][b]; for (int i = 1; i <= n; i++) { answer = min(answer,dist[s][i] + dist[i][a] + dist[i][b]); } return answer; }

from http://kau-algorithm.tistory.com/252 by ccl(A) rewrite - 2021-08-14 20:26:38