백준 1916 - 최소비용 구하기 [C/C++]

1916번: 최소비용 구하기 (acmicpc.net)

문제 설명 및 예시와 출력

 

 반성해야 하는 문제,,, 다익스트라를 써야 한다는 느낌적인 느낌(?)이 들어 금방 끝나겠거니 했지만,,, 골드 문제 답게 구현 자체가 쉽지는 않았다.

 

 초반에 코드 구현은 금방 했고 테스트 케이스도 통과하길래 금방 푼 줄 알았지만,, 메모리 초과가 2%에서 뜨는 문제가 발생했다. 고민 좀 해보다 질문 게시판을 참고한 결과 Priority Queue의 사용으로 한 번에 연산들을 처리해주는 방법을 사용해야 하는 것 같았다.

 

 여기서부터 난관에 빠졌다.. 큐에 들어가야 할 Value가 무엇이 되어야 할까라는 고민이었는데, 생각해보면 단순하지만 거의 한 시간 넘게 이 문제만 잡고 있었다보니 심신미약 상태가 되어버려,, 낑낑대다 결국 해결했다.

 

 일단 메모리 초과 문제는 당연히 Queue에서 나는 것이 자명했으니, 이 큐 안에 들어가야 할 것들의 갯수를 최대한 좀 줄여보고 연산으로써 해결하려고 했다. 그러려면 반드시 Boundary case인 "기존의 Score 값과 새로운 노드를 통과해 가는 Score의 합이 같은 경우" Queue에 넣는 것이 아니라 그냥 Continue 해야 하는 디테일이 필요했다.

 

 아래는 C++로 작성하여 제출한 코드이다.

#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>

#define INF 1e9

using namespace std;
vector<int> score;
vector<vector<pair<int,int>>> mp;
int city, bus, from, to;

void solve() {
    priority_queue<pair<int,int>> q;
    score.assign(city + 1, INF); 

    score[from] = 0;
    q.push(make_pair(0, from));

    while(!q.empty()){
        int cost = q.top().first;
        int cur = q.top().second;
        q.pop();

        if (score[cur] < cost){
            continue;
        }

        for (int i = 0; i < mp[cur].size(); i++) {
            int finalcost = cost + mp[cur][i].first;
            int target = mp[cur][i].second;
            if (score[target] <= finalcost)
                continue;
            score[target] = finalcost;
            q.push({finalcost, target});
        }
        
    }
    cout << score[to] << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> city;
    cin >> bus;
    mp.resize(city + 1); 
    for (int i = 0; i < bus; i++)
    {
        int start, ends, value;
        cin >> start >> ends >> value;
        mp[start].push_back({value, ends});
    }
    cin >> from >> to;
    solve();

    return 0;
}