[프로그래머스] 합승 택시 요금 (2021 카카오 채용 기출) (C++)

Key

플로이드워셜 또는 다익스트라 문제.

 

Idea

"두 사람이 어느 지점까지 같이 가야 택시 요금이 최소가 될까?"

 

각자의 도착 지점이 a, b, 출발 지점이 s, 중간에 각자 가기 시작하는 지점이 k라고 했을 때 요금은 다음과 같다.

graph[s,k] + graph[k,a] + graph[k,b]

어느 지점까지 같이 가야 요금이 최소가 되는지 모르기 때문에 모든 노드(k)를 돌며 최소값을 갱신하면 끝이다.

 

다익스트라 알고리즘으로도 풀 수 있지만, 노드 개수가 최대 200개밖에 안되기 때문에 플로이드 워셜 알고리즘을 사용했다. 기본 플로이드워셜 알고리즘에 아이디어 한줄만 추가하면 되는 문제이기 때문에 아이디어를 생각해냈다면 크게 어렵지 않다.

 

이 때 주의해야할 점이 있다. 요금이 100,000라고해서 INF 값을 100,001로 설정하면 안된다. 스스로 생각해보면 좋을것 같아서 이유를 따로 적지는 않을거다. 검색해보니 이 부분에서 은근 실수를 많이 하는듯하다.

 

Code

#include <string>
#include <vector>
#include <math.h>
#define INF 100000000

using namespace std;

// 노드 개수, 출발노드, a의 도착지점, b의 도착지점, [지점1, 지점2, 사이의 요금]
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    
    vector<vector<int>>v;
    
    v.assign(n+1, vector<int>(n+1, INF));
    
    for(int i=0; i<fares.size(); i++){
        v[fares[i][0]][fares[i][1]]=fares[i][2];
        v[fares[i][1]][fares[i][0]]=fares[i][2];
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) v[i][j]=0;
        }
    }
    
    // 최단거리 갱신
    for(int k=1; k<=n; k++){
        for(int a=1; a<=n; a++){
            for(int b=1; b<=n; b++){
                if(v[a][k]+v[k][b] < v[a][b]){
                     v[a][b]=v[a][k]+v[k][b];
                }
               
            }
        }
    }
    
    // 기본 플로이드워셜 코드에 추가된 아이디어
    for(int i=1; i<=n; i++){
       answer=min(answer, v[s][i]+v[i][a]+v[i][b]);
    }
    
    return answer;
}

 

 

회고

습관적으로 INF를 1e9로 설정하여 바보같은 실수를 했다. vector은 int형인데 최단 거리를 갱신할 때 만약 요금이 INF라면 다음 코드를 실행시키지 않는 조건문을 안넣어서 오버플로우가 발생했다. 생각하면서 풀자 제발