[Programmers] 2021 KAKAO BLIND RECRUITMENT: 합승 택시 요금(C++) / FloydWashall

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

작년 카카오 공채 기출문제

출발지 S에서 목적지 A, B로 가는 최단거리를 계산하는 문제
라서 다익스트라로 생각할 수 있으나
중요한 것은 중간 지점까지는 A와 B가 동승하고 이후에 찢어질 수 있다는 점
그래서 모든 지점에서 모든 지점으로의 최단거리를 계산해야 하기 때문에 플로이드 와샬로 풀어야 한다

예제에서는 위와 같이 노란색 선을 따라 4->1->5(34)의 path로 이동 후
5->6(2) + 5->3->2(46)로 A와 B가 각각 이동하는 것이 최단경로이당 (34+2+46) = 82
따라서 플로이드 와샬로 모든 정점에서의 최단 경로를 구해준 뒤, 모든 정점을 경유지로 가정했을 때의 최소값을 구해주면 끝

#include <iostream> #include <algorithm> #include <string> #include <vector> #define INF 40000005 #define pii pair<int,int> using namespace std; void floyd(int n, vector<vector<int>>& map) { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map[i][j] = min(map[i][j], map[i][k] + map[k][j]); } int solution(int n, int s, int a, int b, vector<vector<int>> fares) { int answer = INF; vector<vector<int>> map(n+1); for (int i = 1; i <= n; i++) { map[i] = vector<int>(n + 1, INF); map[i][i] = 0; } for (auto f : fares) { map[f[0]][f[1]] = f[2]; map[f[1]][f[0]] = f[2]; } floyd(n, map); for (int i = 1; i <= n; i++) answer = min(answer, map[s][i] + map[i][a] + map[i][b]); return answer; } 

나는 원래 infinity값을 987654321로 해주는 습관이 있었는데 이 문제에서는 그런 INF값을 3번 더해줄 가능성이 있기 때문에 overflow가 발생했다
그래서 INF값을 최장거리로 설정해주고 문제를 해결햇당

Time Complexity
: 정점의 개수 - N, 간선의 개수 - M
최초 경로 배열 만들기 -> O(M) <= O(N*(N-1)/2) = O(N^2)
플로이드 와샬 -> O(N^3)
경유지를 거치는 최단거리 구하기 -> O(N)
∴ O(N^2)+O(N^3)+O(N) = O(N^3) (N이 200 이하이기 때문에 충분)