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

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

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

- 접근법

문제를 요약하자면, A,B 각자 목표 종착지가 있고 동일한 지점에서 출발하여 같이 이동할수도 있고, 도중에 찢어져서 각자 종착지를 찾아 갈수있으므로 출발점에서 A,B가 각자 종착지로 모두 도착할동안 최소 COST를 묻는 문제이다.

 

일단 고려해야할 첫번째는, A,B가 같이 이동할수도 있다는 것이다. 어느 지점부터는 찢어져서 각자 종착지를 찾아간다.

물론 A,B가 같이 이동하다가 A,B 중 한명의 종착지에 도달하면 남은 한명이 그때부터 자기의 종착지를 찾아가면 된다.

 

하지만 A,B가 같이 이동하다가 찢어져 각자의 종착지를 찾으러가는 와중에 다시 A,B가 만나서 같이 이동하는 경우는 없다.(최소Cost를 얻는 경로가 될 수 없다)

 

때문에 우리는 이러한 경로를 생각할 수 있다.

 

출발점 S에서 A,B가 같이 출발 -> 어느 노드 X 까지 A,B가 같이 도착 -> X부터 각각 A,B의 종착지까지 각자 이동

 

더 자세히말하자면

Dy[S][X] : S에서 X까지의 가는데 최소 Cost

Dy[X][A] : X부터 A의 종착지까지 A혼자 가는 최소 Cost

Dy[X][B] : X부터 B의 종착지까지 B혼자 가는 최소 Cost

 

즉, Dy[S][X]+Dy[X][A]+Dy[X][B]의 최솟값이 답이 될것이다.

 

그렇다면 Dy[i][j]= i~j까지 가는 최소Cost는 어떻게 얻을까?

많이 보던 점화식으로 짐작했겠지만, N의 최대크기도 200이므로 Floyd 알고리즘으로 해결가능하다.

O(N^3) 시간복잡도이지만 N이 200이므로 충분할것이다.

 

---

- 소스코드

#include <string>
#include <vector>
#include <iostream>
#define INF 999999999
#define MIN(A,B) A>B ? B : A
using namespace std;
int graph[202][202];
void init(int n) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j) graph[i][j]=0;
            else graph[i][j]=INF;
        }
    }
}
void floyd(int n) {
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    init(n);
    int answer = INF;
    int from,to,cost;
    for(int i=0;i<fares.size();i++) {
        from=fares[i][0];
        to=fares[i][1];
        cost=fares[i][2];
        graph[from][to]=cost;
        graph[to][from]=cost;
    }
    floyd(n);
    // start = s , middle = i, end=a,b
    for(int i=1;i<=n;i++) {
        if(graph[s][i]==INF || graph[i][a]==INF || graph[i][b]==INF) continue;
        answer=min(answer,graph[s][i]+graph[i][a]+graph[i][b]);
    }
    return answer;
}