Programmers: 합승 택시 요금 (C++)

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

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

갑자기 프로그래머스 생각나서 오랜만에 들어가 봤다가 확실히 프로그래머스 문제는

문자열 파트나 구현 파트가 조금 더 중요시되는 느낌(?)이었다.

안 그래도 그런 근본적인 부분에서 부족한 느낌이 있는데 제대하고, 프로그래머스도 해야겠다.

암튼 문제들 보면서 풀 수 있을 거 같은 문제를 골라보았다.

 

이 문제는 최단 경로 문제로 플로이드 와샬로 구했다.

모든 거리의 최단 경로들을 구해주고 나서 이 식을 떠올릴 수 있는 게 중요했다.

어떤 지점에서 따로 가면서 a, b의 집으로 따로 갈 때의 최단 경로

즉, 어떤 지점까지 같이 갈 때 경로 + 그 지점으로부터 a까지 경로 + 그 지점으로부터 b까지 경로

answer = min(answer, graph[s][k] + graph[k][a] + graph[k][b]);

[AC 코드]

#include <string>
#include <vector>
#include <cmath>
#define MAX (200 + 1)
#define INF 987654321
using namespace std;

int graph[MAX][MAX];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    // 최솟값을 구하기 위해 answer = INF로 init
    int answer = INF;
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j++){
            if(i == j) continue;
            graph[i][j] = INF;
        }
    }
    
    for(int i = 0; i < fares.size(); i++){
        int s = fares[i][0];
        int e = fares[i][1];
        int w = fares[i][2];
        graph[s][e] = w;
        graph[e][s] = w;
        // 양방향
    }
    
    // floydWarshall
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(graph[i][k] == INF || graph[k][j] == INF) continue;
                if(graph[i][k] + graph[k][j] < graph[i][j]){
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
    
    // 이번 문제 핵심 포인트
    for(int k = 1; k <= n; k++){
        // 갈 수 없는 경로를 포함하고 있으면 패스
        if(graph[s][k] == INF || graph[k][a] == INF || graph[k][b] == INF) continue;
        answer = min(answer, graph[s][k] + graph[k][a] + graph[k][b]);
    }
    return answer;
}