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

https://www.acmicpc.net/problem/1916

N개의 도시와 한 도시에서 다른 도시에 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시로 가는데 드는 최소 비용을 출력하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 100,000
• 0 ≤ 버스 비용 ≤ 100,000

 

가중 그래프의 한 정점에서 다른 정점으로 가는 최소 비용 경로를 구할 때, 다익스트라 알고리즘을 사용한다.

 

다익스트라 알고리즘

• link-state routing algorithm에도 사용됨
  • N': 최소 비용 경로가 알려진 노드 집합
  • D(v): source 노드에서 v로 가는 현재 비용
  • p(v): source 노드에서 v로가는 경로에 대한 조상 노드
  • c(x,y): x 노드에서 y 노드로 가는 비용 (갈 수 없으면 무한대)
• N'에 없는 각 노드로 가는 비용에서 최솟값을 골라 그 노드를 N'에 추가하면서 진행
  • 최솟값인 노드를 선택하고 추가하기 위해 우선순위로 알아서 추가되는 priority queue로 구현해야 함
    • 원소에 - 를 붙여 저장하면 오름차순으로 저장할 수 있음 (기본값: 내림차순)

다익스트라 알고리즘 예시

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M 입력받기
2. M개의 버스 정보 입력받기 (출발지, 도착지, 비용)
3. 거리 배열을 1e9로 초기화
4. 출발지와 도착지를 입력받고 다익스트라 함수 돌리기
5. 출발지에서 도착지까지 가는데 드는 최소 비용 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int,int>
using namespace std;

int n,m,u,v,w,s,e,dist[100001];
vector<pii> vec[100001];

void dijk(int start) {
    priority_queue<pii> pq;
    pq.push({start,0});
    dist[start] = 0;
    
    while (!pq.empty()) {
        int cur = pq.top().first, d = -pq.top().second;
        pq.pop();

        if (dist[cur]<d) continue;
        for (auto i : vec[cur]) {
            int cost = d + i.second;
            if (cost < dist[i.first]) {
                dist[i.first] = cost;
                pq.push({i.first,-cost});
            }
        }
    }
}

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

    cin >> n >> m;
    for (int i=0; i<m; i++) {
        cin >> u >> v >> w;
        vec[u].push_back({v,w});
    }

    fill(dist,dist+100001,1e9);

    cin >> s >> e;
    dijk(s);
    cout << dist[e];
}