프로그래머스 : 합승 택시 요금

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

프로그래머스

 

softeer의 출퇴근길과 비슷한 느낌을 받았다!!

https://softeer.ai/practice/6248

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

---

A, B의 퇴근루틴을 생각해보면

 

1. 시작점 -> 나눠타는 지점

2. 나눠타는 지점 -> A의 집

3. 나눠타는 지점 -> B의 집

각각의 cost를 다 더해주면된다.

 

이걸 그대로 하나하나 구해보면, 전체탐색밖에 답이 안보인다!!!! softeer때처럼 반대로 생각해보자

 

1. 시작점 -> A,B의 합류점

2. A의 집 -> 합류점

3. B의 집 -> 합류점

 

나눠타는 지점을, 합류점으로 생각해보면,,!! 각각의 합류점마다, 3개의 출발지로부터의 최소cost를 구할 수 있고 (다익스트라)

이걸 다 더해봤을 때, 최소cost를 가지는 합류점을 선택해주면 된다.

 

softeer에서

 

1. 회사 -> 어딘가

2. 어딘가 -> 집

를 찾을 때

 

1. 회사 -> 어딘가

2. 집 -> 어딘가

로 바꿔서 생각한것과 비슷했다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

이걸 풀어봤는데도 바로 생각 못하고 찾아봤다니이ㅣㅣㅣㅣㅣㅣㅣㅣ

분발하자

 

---

#include <string>
#include <vector>
#include <climits>
#include <iostream>

using namespace std;

vector<vector<int>> cost;

vector<long long> min_cost(int s, int n){
    vector<long long> result(n+1, LONG_MAX);
    vector<bool> check(n+1, false);
    int limit = n;
    
    result[s] = 0;
    check[s] = true;
    limit--;
    
    while(limit > 0){
        // 지금위치에서 갈수있는곳들 업데이트
        for(int i = 1; i<=n; i++){
            if(cost[s][i] == 0){
                continue;
            }
            result[i] = min(result[i], result[s] + (long long)cost[s][i]);
        }
        
        // 다음위치 찾기 (최소값을 가지는친구)
        int next;
        long long next_cost = LONG_MAX;
        for(int i = 1; i<=n; i++){
            if(check[i]){
                continue;
            }
            if(next_cost > result[i]){
                next = i;
                next_cost = result[i];
            }
        }
        limit--;
        s = next;
        check[s] = true;
        
    }
    return result;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    cost = vector<vector<int>>(n+1, vector<int>(n+1, 0));
    
    for(int i = 0; i<fares.size(); i++){
        cost[fares[i][0]][fares[i][1]] = fares[i][2];
        cost[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    
    vector<long long> stohap = min_cost(s, n);
    vector<long long> atohap = min_cost(a, n);
    vector<long long> btohap = min_cost(b, n);
    
    long long result = LONG_MAX;
    
    for(int i = 1; i<=n; i++){
        if(stohap[i] == LONG_MAX || atohap[i] == LONG_MAX || btohap[i] == LONG_MAX){
            continue;
        }
        long long temp = stohap[i] + atohap[i] + btohap[i];
        result = min(result, temp);
    }
    
    return result;
}