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

 이 문제는 플로이드 워셜을 사용해서 푸는 문제이다. 정점의 개수가 최대 200개로, O(n^3) = 800만이므로 시간 안에 충분히 계산이 가능하다. INF 값을 적절히 할당하는 것이 중요한데, 정점 개수가 최대 200개이고 간선의 가중치가 최대 10000 이므로 2억이라고 단순 계산했다. 따라서 그것보다 큰 3억으로 INF를 설정했고, 정답을 맞출 수 있었다. 처음에는 그래프와 가중치가 나와서 다익스트라를 생각했지만, 여러 쌍의 경우를 전부 알아야 하므로 플로이드 워셜이 효율적이라 생각해서 문제를 풀었다.

 

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define INF 300000000

int dist[201][201];

void init() {
    for (int y = 0; y < 201; y++) {
        for (int x = 0; x < 201; x++) {
            if (y == x) {
                dist[y][x] = 0;
                continue;
            }
            dist[y][x] = INF;
        }
    }
}

void floyd_warshall(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

// s : 출발 지점, a와 b : 도착 지점
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    // 초기화
    init();
    dist[s][s] = 0;
    for (vector<int> fare : fares) {
        int c = fare[0];
        int d = fare[1];
        int cost = fare[2];
        
        dist[c][d] = cost;
        dist[d][c] = cost;
    }
    
    floyd_warshall(n);
    
    // 처음 answer : 따로 갔을 때의 답 - 처음 갈라지기 시작한 위치가 s
    int answer = dist[s][a] + dist[s][b];
    for (int i = 1; i <= n; i++) {
        if (i == s) {
            continue;   // 이미 계산했으므로
        }
        
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
    }
    
    return answer;
}