[프로그래머스] 합승 택시 요금 - 2021 KAKAO BLIND RECRUITMENT

⚙️ 알고리즘 분류 : 최단 경로

🔠 언어 : c++

🤫 힌트.

방문해야 하는 node의 개수가 적다. 가중치와 node. 뭔지 RGRG?

✏️ 풀이.

node와 가중치. 딱 보자마자 최단 경로인 걸 알았다.
'플로이드 와샬'을 쓴 이유는 힌트에 적힌 대로 방문해야 하는 node 개수가 적고, 문제에서 같이 합승하는 구간이 '경유지'라고 생각했기 때문이다.

⚠️ 헤맨 부분.

플로이드 와샬로 풀다가 '경유지와 a,b를 어떻게 고려하지?'하며 점화식을 바꾸는 것에 집중했다. 아마 여기가 함정이었던 듯.

일단 최단 경로를 다 구하고 나서, 경로의 값들을 더해보며 최소값을 찾으면 됐을 것인디~

👩🏻‍💻 코드.

#include <string>
#include <vector>
#define mp make_pair
#define MX 99999999
using namespace std;
vector<pair<int, int>> v[201];
int dist[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = MX;
    // node 간의 거리를 0 또는 MX로 초기화
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) {
            dist[i][j]= (i==j)?0:MX;
        }
    }
    
    // 길이 있는 node는 쌍방으로 가중치 체크
    for(int i=0; i<fares.size(); i++){
        int s=fares[i][0], e=fares[i][1], p=fares[i][2];
        v[s].push_back({e,p});
        v[e].push_back({s,p});
        dist[s][e]=dist[e][s]=p;
    }
    
    // 플로이드 와샬 알고리즘! 바꿀 생각 말고 걍 일단 써라.
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    
    // 구한 값들로 합의 최소값을 찾아보자!
    for(int k=1; k<=n; k++){
        answer=min(answer, dist[s][k]+dist[k][a]+dist[k][b]);
    }
    return answer;
}

😎 후기.

딱 보자마자 최단 경로인 걸 알았다. 문제를 풀다보면 대부분 다익스트라 or 플로이드 와샬인데, node 개수가 적어서 플로이드 와샬로 풀었다.

저번에 한 번 푼 문젠데, 그땐 안 보고 풀었지만 이번엔 내 과거의 코드를 보고 풀었다... 왜 과거 보다 못한 걸까...?

그리고 다른 사람이 푼 방식을 보니까 다익스트라로 푼 경우도 있었다.
플로이드 와샬 하다가 아닌 것 같아서 다익스트라로 바꿨는데, 다익스트라는 단일 경로라서 '경유지랑 a,b 관계를 나타내야 할 것 같은데... 어떡하지?' 하며 곤란해 했었다.
다익스트라로 푼 경우를 보고 '이런 식으로도 풀 수 있구나!' 싶었지만, 잘 생각해내진 못할 것 같다... 그치만 나도 언젠간 알고리즘 마스터가 될 수 있겠지😎