14) 프로그래머스 Lv.3 - 합승 택시 요금

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

오랜만에 다익스트라 리마인드할 겸 풀었다.

// 1. 다익스트라 사용
// 2. 구해야 할것
// 2-1. 처음부터 혼자 가는 비용
// 2-2. 중간까지 같이 갔다가 혼자 가는 비용
// 3. 2-1, 2-2 가장 작은 수 구하기

#include <bits/stdc++.h>

using namespace std;

int vertex[201]; // 정점으로 부터의 비용 저장
vector<pair<int, int> > dij[201]; // 그래프 저장
int INF = 4000001;

void dijkstra(int start, int arrive) {
    // 시작 Node = s
    fill_n(vertex, 201, INF);
    vertex[start] = 0;
    priority_queue<pair<int, int> > q;
    // 출발 node 저장 (비용 우선순위 저장으로 q의 first = 비용)
    q.push(make_pair(-vertex[start], start));
    
    
    while(!q.empty()) {
        int start_node_vertex = -q.top().first;
        int start_node = q.top().second;
        q.pop();
        if(start_node == arrive) {
            break;
        }
        for(int i = 0; i < dij[start_node].size(); i++) {
            int target = dij[start_node][i].first;
            if(vertex[target] > dij[start_node][i].second + vertex[start_node]) {
                vertex[target] = dij[start_node][i].second + vertex[start_node];
                q.push(make_pair(-vertex[target], dij[start_node][i].first));
            }
        }
    }
}

// n : node수 , s : 출발지 , a : A도착지 , b : B도착지
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    // dij Vector에 그래프 저장
    for(int i = 0; i < fares.size(); i++) {
        dij[fares[i][0]].push_back(make_pair(fares[i][1], fares[i][2]));
        dij[fares[i][1]].push_back(make_pair(fares[i][0], fares[i][2]));
    }
    
    int alone = 0;
    dijkstra(s, a);
    alone += vertex[a];
    dijkstra(s, b);
    alone += vertex[b];
    answer = alone;
    int together;
    for(int i = 1; i <= n; i++) {
        together = 0;
        dijkstra(s, i);
        together += vertex[i];
        dijkstra(i, a);
        together += vertex[a];
        dijkstra(i, b);
        together += vertex[b];
        if(answer > together) answer = together;
    }
    
    return answer;
}

처음에 중간까지 같이 갈 수 있는지 모르고 일단 풀었지만 문제를 다시 읽어보고 다시 푼 문제.

사실상 모든 노드를 방문하면서 비교해야하기 때문에 시간 초과에 걸릴 줄 알았지만 의외로 성공한 문제였다.

 

Dijkstra

1. 출발지와 도착지를 정한다.

2. vertex 1차 배열을 통해 최소 비용을 체크한다.

3. dij 2차 Vecter을 통해 그래프를 저장한다.

4. 시작 지점의 vertex 값은 0으로 설정하고 priority_queue에 넣는다 (비용과 노드 번호 같이)

5. priority_queue의 top에서 노드 번호(s 라고 가정)를 가져온다.

6. 가져온 노드 번호를 활용해서 dij에 저장된 그래프를 참고하여 이어진 모든 수들 중 조건에 맞는 수들만 priority_queue에 넣는다.

6-1. priority_queue에 넣는 조건은 연결된 노드를 target이라고 할 때, vertex[target]의 값이 노드 s에서 노드 target으로 가는 비용과 노드 s에서의 vertex 비용의 합 보다 더 클때만 넣는다.

7. 도착하거나 queue에 값이 없으면 끝.

 

---

모든 노드를 방문하는 것은 Dijkstra도 이번 문제처럼 풀 수 있겠지만, 플로이드 와샬이라는 알고리즘을 알게 된다면 더욱 간단하게 해결할 수 있다고 한다. 다음 알고리즘 연습은 플로이드 와샬을 공부해볼 예정이다.