(C++)2021 KAKAO BLIND RECRUITMENT 합승 택시 요금

1. 문제

programmers.co.kr/learn/courses/30/lessons/72413?language=cpp

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

 

 

2. 풀이

S에서 A와 B로 이동할때, 함께 이동할 수 있다고 한다면,

어디까지 이동한 뒤 따로 이동해야 최단 요금으로 이동할 수 있는지 묻는 문제였다. 

 

나는 이를  S -> A까지 가는 방법을 계속 min값으로 업데이트 하는 방식으로 문제를 풀었다. 

 

즉, S에서 A로 가는 방식은

1) S -> A : 50

 

2) S -> (1 -> A) : 10+25 = 35 

35로 업데이트

 

3) S -> 1 ->5 ->A : 40 + 24+ 2 = 66 = 업데이트 X

 

이런 식으로 계속 부분으로 쪼갤 수 있는데, 새로운 길은 = 기존의 길의 최단 거리의 합 인 부분에서 착안하여 

"다이나믹 프로그래밍" 으로 풀었다. 

 

내가 작성한 알고리즘은 시작 -> 중간지점 -> 끝  을 반복하여 for문으로 최단거리를 계속 갱신하는 방법이다. 

아래의 코드에서 k가 중간지점이다.

for (int k = 0; k < n; k++){
        //i에서 j로 갈때
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (i == j || i == k || k == j) continue;
                
                //i -> j -> k로 이동할 때, 경로가 있다면... 
                if(dynamic_list[i][k] != MAXSIZE && dynamic_list[k][j] != MAXSIZE){
                    dynamic_list[i][j] = findmin(dynamic_list[i][j], dynamic_list[i][k] + dynamic_list[k][j]);
                } 
            }
        }
    }

 

이렇게 포문을 돌려 모든 경우에 대한 최단 거리를 찾아준 후, 

포문을 돌려, 모든 점 i 에 대해

(S -> i) + (i -> A) + (i -> B) 가 최소가 되는 지점을 찾았다.  

 

 

3. 코드

#include <string>
#include <vector>
#define MAXSIZE 9999999
using namespace std;

int findmin(int a, int b){
    if(a < b) return a;
    else return b;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    vector<vector <int>> dynamic_list;
    
    for (int i = 0; i < n ;i++){
        vector <int> element;
        for(int j = 0; j < n; j++){
            //경로가 없을 때
            element.push_back(MAXSIZE);
        }
        dynamic_list.push_back(element);
    }
    
    for(int i = 0; i < fares.size();i++){
        int x = fares[i][0];
        int y = fares[i][1];
        int d = fares[i][2];
        dynamic_list[x-1][y-1] = d;
        dynamic_list[y-1][x-1] = d;
    }
    
    for(int i = 0;i< n;i++){
        dynamic_list[i][i] = 0;
    }
    
    //중간점 k
    for (int k = 0; k < n; k++){
        //i에서 j로 갈때
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (i == j || i == k || k == j) continue;
                
                //i -> j -> k로 이동할 때, 경로가 있다면... 
                if(dynamic_list[i][k] != MAXSIZE && dynamic_list[k][j] != MAXSIZE){
                    dynamic_list[i][j] = findmin(dynamic_list[i][j], dynamic_list[i][k] + dynamic_list[k][j]);
                } 
            }
        }
    }
    
    //중간점이 없을 때가 최소
    answer = dynamic_list[s-1][a-1] + dynamic_list[s-1][b-1];
    
    for (int i = 0; i < n; i++){
        //경로가 모두 있으면
        if (dynamic_list[s-1][i] != MAXSIZE && dynamic_list[i][a-1] != MAXSIZE && dynamic_list[i][b-1] != MAXSIZE){
            answer = findmin(answer, dynamic_list[s-1][i] + dynamic_list[i][a-1] + dynamic_list[i][b-1]);
        }
    }

    return answer;
}

 

 

4. 그 외

거리가 100000 아래라고 하여 아무생각 없이 MAX 값을 100001로 두었는데 계속 틀렸다고 했었다.

이유는 내가 하나의 거리를 찾는게 아니고, 거리들의 합을 찾는 것이었기 때문에 그렇게 두면 틀렸던 것이었다.

최댓값을 9999999로 바꿔주니 해결되었다,.,,

 

오늘의 교훈,,, 코테 max값은 무조건 9999999로 두자