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

 

oh oh 문제부터 너무 길어서 당황스럽고~

 

• IDEA (우선 이건 개망한 아이디어라는 점★)

이차원 vector 만들어서 지점을 index로 사용하고 각각 연결된 곳에 요금을 입력하기

dfs 사용하여 완전탐색 실행하기

연결되지 않은 곳은 0으로 채워서 출발점부터 시작,

방문 여부 체크하는 일차원 벡터 만든다음 방문 처리하기

index 1부터 시작해서 index 끝까지 반복문 돌리고

0이 아닌 곳 + 이전에 방문하지 않은 곳 만나면 dfs(재귀)

+ 이렇게 노가다 해보다가 생각난건데

그냥 출발점에서 A B 둘다 방문처리 될 때 까지 재귀를 돌릴게 아니라

S -> A / S -> B 이렇게 각각 가는게 더 저렴한 경우도 있을거고,

S-> A / S -> B 가는 경우도 최소요금이 있을테니까

 

재귀를 총 3번

 - case 1) S부터 A까지 최소요금 찾기

 - case 2 ) S부터 B까지 최소요금 찾기 

 - case 3 ) A부터 B까지 최소요금 찾기 (A -> B // B -> A는 요금이 동일하니까)

이렇게 돌린 다음에

1 + 2 랑 1 + 3, 2 + 3 중에 최소를 찾으면 최소 요금을 더 빠르게 찾을 수 있지 않을까?

 

• 1차 구현

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void dfs(vector<vector<int>>link, vector<vector<int>>money, vector<bool>visit, int st, int end, int cnt, int&ans){
    visit[st] = 1;
    cout << cnt << "++";
    if(visit[end]){
        ans = min(cnt, ans);
        return;
    }
        
    for(int i =0; i < link[st].size(); ++i){
        if(!visit[link[st][i]]){
            cnt += money[st][i];
            if(cnt > ans) return;
            dfs(link, money, visit, link[st][i], end, cnt, ans);
            cnt -= money[st][i];
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    vector<vector<int>> link(n+1); // 연결 입력 vector
    vector<vector<int>> money (n+1); // 요금 입력 vector
    for(auto x : fares){
        link[x[0]].push_back(x[1]);
        link[x[1]].push_back(x[0]);
        money[x[0]].push_back(x[2]);
        money[x[1]].push_back(x[2]);
    } // 연결된 길 + 요금 입력
    
    vector <bool> visit (n+1, 0); // 이전에 방문했는지 여부 확인용
    int s_a = 10000000;
    dfs(link, money, visit, s, a, 0, s_a);
    cout << "\n" << s_a << "\n";

    int s_b = 10000000;
    dfs(link, money, visit, s, b, 0, s_b);
    cout << "\n" << s_b << "\n";

    int a_b = 10000000;
    dfs(link, money, visit, a, b, 0, a_b);
    cout << "\n" << a_b << "\n";

    int answer = min(s_a + s_b, min(s_a + a_b, s_b + a_b));
    return answer;
}

이러면 첫번째 case인  중간에 갈라서는게 구현이 안된다

아니 샤갈 중간에 갈라설거면 각자 가라고ㅠㅠ

 

찾아보니까 다익스트라 알고리즘을 활용해야한다고 하길래

다익스트라 알고리즘을 먼저 공부하고 오기로!

• IDEA2 

이차원 vector 만들어서 지점을 in

shortest path관련 강의를 듣다보니까

all pairs shorest path 에 대한 내용이 있어서 이걸 적용해보면 조금 더 쉽게 풀 수 있지 않을까 하는 생각이 들었음.

각 노드간의 거리 최소를 싹 구한 다음에

st지점에서 특정 지점까지의 거리+거기서 a까지 + 거기서 b 까지 중 최소를 구하면 될 것 같음!

 

• 2차구현

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

#define INF 1e9  // 무한대 (도달 불가능한 초기값)

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    vector<vector<int>> v(n+1, vector<int>(n+1,INF)); // (지점, 요금)
    for(auto x : fares){
        v[x[0]][x[1]] = x[2];
        v[x[1]][x[0]] = x[2];
    } // 이차원 배열로 저장
    for(int i = 1; i <= n; ++i) v[i][i] =0; // 자기자신은 0

    vector<vector<int>>d = v;

    for(int k = 1; k<=n; k++){
        for(int i =1; i<=n; i++){
            for(int j=1; j<=n; ++j){
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    } // floyd-warshall algorithm 활용 == all pairs shorest path

    //for(auto i : d){ for(auto j : i){cout << j << " ";}cout <<  "\n";} //확인용 출력

    int ans = INF;
    for(int i = 1; i<=n; i++) {
        if(ans > (d[s][i] + d[i][a] + d[i][b])) ans = d[s][i] + d[i][a] + d[i][b];
        //cout << ans << " ** "; 확인용 출력
    }

    return ans;
}

 

이렇게 오류가 나와서 확인해보니까 INF 끼리 더하면 정수 범위를 초과해서 음수로 바뀌는 오류가 발생하는 듯

그래서 조건에 내가 찾는 값 중 INF 가 껴있으면 계산을 하지 않고 넘기는 것을 추가했음.

 

•  최종 구현

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

#define INF 1e9  // 무한대 (도달 불가능한 초기값)

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    vector<vector<int>> v(n+1, vector<int>(n+1,INF)); // (지점, 요금)
    for(auto x : fares){
        v[x[0]][x[1]] = x[2];
        v[x[1]][x[0]] = x[2];
    } // 이차원 배열로 저장
    for(int i = 1; i <= n; ++i) v[i][i] =0; // 자기자신은 0

    vector<vector<int>>d = v;

    for(int k = 1; k<=n; k++){
        for(int i =1; i<=n; i++){
            for(int j=1; j<=n; ++j){
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    } // floyd-warshall algorithm 활용 == all pairs shorest path

    //for(auto i : d){ for(auto j : i){cout << j << " ";}cout <<  "\n";} //확인용 출력

    int ans = INF;
    for(int i = 1; i<=n; i++) {
        if(d[s][i] == INF || d[i][a] == INF || d[i][b] == INF) continue; // int 범위 초과로 인한 오류 방지용
        if(ans > (d[s][i] + d[i][a] + d[i][b])) ans = d[s][i] + d[i][a] + d[i][b];
        //cout << ans << " ** "; 확인용 출력
    }

    return ans;
}

성공~!

 

10월 12일에 처음 시작해서

물론 뜨문뜨문 보긴 했지만 11월 5일에 풀어냈다

혼자 힘으로 해서 더 기분 좋음!!!!

 

floyd-warshall algorithm 공부한거는

블로그에 추가로 업로드할 예정!

 

+++) 다른 사람들이 푼 거 보니까 다익스트라로 시작점을 s, a, b로 각각 구한다음에

그 만나는 값이 최소가 되는 점을 찾는 방법으로도 풀 수 있나보다

이건 나중에 혼자서 한번 풀어보고 추가해야겠다.