백준_1916_최소비용 구하기[C++]

[문제링크]

문제 접근

다익스트라로 접근하였다.

---

코드 분석

1. Global parameters

#define MAXSIZE 100001 
vector<vector<pair<int, int>>> vec(MAXSIZE);
int N, M;

간선의 정보를 담을 vec을 전역 변수를 선언하였다. 문제에 따르면 Directed-Weighted-Graph이다. 그렇기에 {정점의 번호,가중치}를 저장할 수 있도록 pair로 선언해줬다.

2. insertEdge function

void insert(int v1, int v2, int cost) {
    vec[v1].push_back({v2, cost});;
    return;
}

자세한 설명은 생략한다.

3. Main Logic (Dijkstra)

void dijkstra(int start, int end) {
    int dict[MAXSIZE];
    for (int i = 1; i <= N; i++) dict[i] = 999999999; //set infinty
    //set start point
    dict[start] = 0;
    priority_queue<pair<int, int>> q;
    q.push({start, 0});
    //do dijkstra
    while (!q.empty()) {
        int cur_vid = q.top().first;
        int cur_cost = -q.top().second;
        q.pop();

        if (dict[cur_vid] < cur_cost) continue;
        for (int i = 0; i < vec[cur_vid].size(); i++) {
            int next_vid = vec[cur_vid][i].first;
            int next_cost = cur_cost + vec[cur_vid][i].second;
            if (dict[next_vid] > next_cost) {
                dict[next_vid] = next_cost;
                q.push({next_vid, -next_cost});
            }
        }
    }
    cout << dict[end] << "\n";
}

• line 1 : 거리를 저장해줄 dict 배열을 생성한다.
• line 2 : 배열의 모든 값을 무한대로 초기화한다.
• line 5 : 초기에 탐색하는 점을 0으로 세팅한다.
• line 6~7 : 우선순의 큐를 선언하고 처음 탐색하게 되는 점과 비용(0)을 삽입한다.
• line 10~23 : Dijstra 알고리즘을 진행한다.
• line 24 : 정답을 출력한다.

흐름은 쉽다. 탐색을 진행하면서 현재 시점에서 도달가능한 점의 값, 코드상의 dict[next_vid] 값이 현재 축적한 비용보다 크다면 dict[next_vid] 값을 next_cost로 update해주고 우선순의 큐에 넣어주면 된다.

## Full Code

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
#define MAXSIZE 100001
vector<vector<pair<int, int>>> vec(MAXSIZE);
int N, M;

void insert(int v1, int v2, int cost) {
    vec[v1].push_back({v2, cost});;
    return;
}

void dijkstra(int start, int end) {
    int dict[MAXSIZE];
    for (int i = 1; i <= N; i++) dict[i] = 999999999; //set infinty
    //set start point
    dict[start] = 0;
    priority_queue<pair<int, int>> q;
    q.push({start, 0});
    //do dijkstra
    while (!q.empty()) {
        int cur_vid = q.top().first;
        int cur_cost = -q.top().second;
        q.pop();

        if (dict[cur_vid] < cur_cost) continue;
        for (int i = 0; i < vec[cur_vid].size(); i++) {
            int next_vid = vec[cur_vid][i].first;
            int next_cost = cur_cost + vec[cur_vid][i].second;
            if (dict[next_vid] > next_cost) {
                dict[next_vid] = next_cost;
                q.push({next_vid, -next_cost});
            }
        }
    }
    cout << dict[end] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    while (M--) {
        int v1, v2, cost;
        cin >> v1 >> v2 >> cost;
        insert(v1, v2, cost);
    }
    int start, end;
    cin >> start >> end;
    bfs(start, end);
}

회고

계속 시간초과가 떴다. 만약 dict[cur_vid] < cur_cost이라면 dict[cur_vid]는 최소비용이 이미 저장되어있다는 것이 보장이 된다. 그렇기에 해당 조건을 만족하면 continue를 진행하면 된다.