[백준/c++] 1916번: 최소비용 구하기

 

 

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

1916번: 최소비용 구하기

 

문제 요약

 

N개의 도시.

한 도시에서 다른 도시에 도착하는 M개의 버스.

A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용

 

 

입력 형태

도시 개수(N, 1 ≤ N ≤ 1,000)

버스 개수(M, 1 ≤ M ≤ 100,000)

버스 정보(버스 출발 도시 번호, 버스 도착 도시 번호, 버스 비용) * M

출발점 도시 번호 + 도착점 도시 번호

 

---

 

 

시작점에서 도착점까지 최소 비용으로 가야 하는 문제로 모든 정점을 돌면서 최소 비용을 계산하면 된다. (다익스트라 문제)

코드를 하나하나 분석해보자.

 

• 입력받기

vector<pair<int, int>> busInfo[NUM];

void input(){
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int from, to, w;
        cin >> from >> to >> w;
        busInfo[from].push_back({to, w});
    }
    cin >> start >> destination;
}

버스의 출발점, 도착점, 걸리는 비용을 담는 벡터를 선언해줬다. 도착점과 걸리는 비용을 pair로 묶어서 넣어줬다.

busInfo[출발점].push_back({도착점, 비용})

 

• priority_queue

#include <queue>

struct Info{
    int index, dis;
    Info(){}
    Info(int index, int dis) : index(index), dis(dis) {}
    bool operator<(const Info& in) const{
        return dis > in.dis;
    }
};

void solution(){
    priority_queue<Info> q;
    //...
}

구조체 Info를 만들었는데, 이 구조체는 정점 인덱스(도시 번호)와 비용을 담고 있다. 

이 구조체 내에서 우선순위 큐의 우선순위를 정해 값을 정렬할 수 있다. 

 

 

• 최소 비용 구하기

void solution(){
    priority_queue<Info> q;
    for(int i = 1; i<=n; i++) dist[i] = 0x7fffffff;     //모든 정점 초기화 -> infinite
    q.push({start, 0});     //1: index, 2: dist[]값
    dist[start] = 0;        //시작점은 0
    
    while(!q.empty()){
        Info infor = q.top();
        q.pop();
        
        if(dist[infor.index] != infor.dis) continue; //시작점에서 index까지의 거리가 dis(최신정보)와 다르면 패스
        
        //연결된 정점에 대한 정보 갱신
        for(auto& j : busInfo[infor.index]){
            auto [to, weight] = j;
            if(dist[infor.index] + weight >= dist[to]) continue;
            dist[to] = dist[infor.index] + weight;
            q.push({to, dist[to]});
        }
    }
    cout << dist[destination] << '\n';
}

{시작점, 비용(0)}을 우선순위 큐에 넣고, dist[시작점]=0

시작점에 대한 정보(Information)를 기록에 추가하고, 거리 배열(dist)에 갱신해준다.

우선순위 큐에서 가장 앞에 나와있는(top) 값을 뽑아서 연결 정점 정보 갱신을 진행한다.

 - 만약 시작점에서 우선순위 위에 저장된 Info.index까지의 거리가 최신 거리 배열(dist)과 다르다면, 패스 -> 예전 정보

 - 연결된 정점에 대한 정보 갱신

    - j : infor.index와 연결된 정점 (반복문을 돌며 가리키는 정점이 변경됨)

    - to :  j 인덱스, weight: j까지의 가중치

    - dist [j] : 지금까지 계산된 거리

    - dist [infor.index] : 시작점부터 방문완료한 j의 연결노드의 거리(방문하지 않은 노드 아님)

    - dist[infor.index] + weight : 시작 노드 -> infor.index -> j의 거리

    - 만약 infor.index를 거치고 오는 것이 시작 노드에서 바로 오는 것보다 빠르다면 해당 값으로 업데이트

 

 

---

 

 

[전체 코드]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define NUM 1002
using namespace std;
int n, m, start, destination, dist[NUM];
vector<pair<int, int>> busInfo[NUM];

struct Info{
    int index, dis;
    Info(){}
    Info(int index, int dis) : index(index), dis(dis) {}
    bool operator<(const Info& in) const{
        return dis > in.dis;
    }
};

void input(){
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int from, to, w;
        cin >> from >> to >> w;
        busInfo[from].push_back({to, w});
    }
    cin >> start >> destination;
}

void solution(){
    priority_queue<Info> q;
    for(int i = 1; i<=n; i++) dist[i] = 0x7fffffff;     //모든 정점 초기화 -> infinite
    q.push({start, 0});     //1: index, 2: dist[]값
    dist[start] = 0;        //시작점은 0
    
    while(!q.empty()){
        Info infor = q.top();
        q.pop();
        
        if(dist[infor.index] != infor.dis) continue; //시작점에서 index까지의 거리가 dis(최신정보)와 다르면 패스
        
        //연결된 정점에 대한 정보 갱신
        for(auto& j : busInfo[infor.index]){
            auto [to, weight] = j;
            if(dist[infor.index] + weight >= dist[to]) continue;
            dist[to] = dist[infor.index] + weight;
            q.push({to, dist[to]});
        }
    }
    cout << dist[destination] << '\n';
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

사실 이번 문제는 다른 사람의 코드를 참조했다. priority_queue 사용법에 익숙하지 않아서였는데, 하고 보니까 queue와 별로 다를 게 없었다. compare에 우선순위를 정해주면 되는 것이었다. 그리고 구조체 Info를 만들어서 좀 더 깔끔하고 멋진 코드를 만들 수 있었다. 이런 형태를 익혀서 다른 문제에도 사용할 수 있도록 해야겠다.

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!