[C++] 백준/BOJ - 11779 : 최소비용 구하기 2

---

문제 이해 단계

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

11779번: 최소비용 구하기 2

n개의 도시와 m개의 버스가 존재한다.
버스는 A도시에서 출발하여 B도시에 도착하는 정보로 주어진다.

그리고 각 버스마다 드는 비용이 존재한다.

또한 입력으로 출발지와 도착지가 주어질 때,
출발지에서 도착지까지 가는데 드는 최소 비용과 경로를 출력하는 것

 

 

---

문제 접근 단계

일단 문제 조건부터 살펴보자. 도시의 개수 n은 최대 1,000
간선의 개수(버스의 개수)와 버스 비용은 100,000까지이다.

---

키워드 분석

해당 문제를 풀기 위한 키워드를 분석해 보자. 당연히 최소비용과 경로일 것이다.

그래프 문제에서 최소비용을 따지는 것이 나오면
DFS, 다익스트라, 플로이드 워셜 등이 생각나는데, 이 문제의 특징을 생각해 보자.

해당 문제에서는 입력으로 출발지와 도착지를 정해준다.
출발지를 정해주기 때문에 한 정점의 입장에서만 봐주면 된다.

그렇기 때문에 한 정점에서 다른 정점으로 가는 최단거리를 구하는
다익스트라 알고리즘이 가장 적절하다.

그렇게 해서 도착 지점까지를 구하면  그게 최소 비용이 될 것이다.

 

---

경로 구하기

이제 다음 문제는 최소 비용으로 가는 경로를 어떻게 구하냐이다.
여기서 일반적으로 사용하는 것이"경로 추적" 알고리즘이다.

사실 거창하게 이름이 붙어있긴 하지만 원리는 간단하다.

parent [A] = B : A의 부모는 B이다.
여기서는 B번 도시에서 출발하여 A번 도시로 도착했다는 뜻이다.

이런 식으로 역추적하는 방식으로 경로를 추적할 수 있다.

자세한 방식은 문제 구현 단계에서 보도록 하겠다.

 

 

---

문제 구현 단계

cin >> n >> m;

for(int i = 0; i < m; i++){
    int v1, v2, v3;
    cin >> v1 >> v2 >> v3;
    bool flag = false;

    for(int i = 0; i < v[v1].size(); i++){
        //해당 출발지와 도착지와 동일한 입력이 들어왔다면
        if(v[v1][i].first == v2){
            flag = true;
            // 비용이 더 작은 것으로 갱신
            if(v[v1][i].second > v3) v[v1][i].second = v3;
            break;
        }
    }
    if(!flag) v[v1].push_back({v2,v3});
}
int start,end;
fill(d,d+1001,INF);
for(int i = 0; i <= n; i++) parent[i] = i;
cin >> start >> end;

일단 입력을 받는 부분이다.

문제에 나와있지 않지 않지만, 출발지와 도착지가 같은데 비용만 다른 경우가 있다.
이런 경우에는 그 값을 경신시켜줘야 한다.

그리고 start에서 출발해서 다른 정점으로 갈 때의 최소거리를 담아둘 배열 d를 INF로 초기화한다.
여기서 INF를 너무 작은 값으로 초기화하지 않도록 주의한다.

INF는 정점의 개수 * 비용보다는 커야 하므로
1,000 * 100,000 = 10^9보다는 커야 한다.

INT를 넘어가기 때문에 연산을 할 때 자료형을 long long으로 해줬다.

그리고 parent의 정점을 초기화하는데, 자기 자신을 가리키도록 초기화한다.

vector<int> path;
int parent[1001];
void findParent(int x){
    path.push_back(x);
    if(parent[x] == x) return;
    findParent(parent[x]);
}

// 다익스트라 알고리즘
void daijkstra(int num){
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,
greater<pair<long long,int>>> q;
    d[num] = 0;
    q.push({0,num});
    while(!q.empty()){
        int x = q.top().second;
        long long cost = q.top().first;
        q.pop();
        for(int i = 0; i < v[x].size(); i++){
            int nx = v[x][i].first;
            long long nCost = v[x][i].second + cost;
            if(d[nx] > nCost){
                parent[nx] = x;
                d[nx] = nCost;
                q.push({nCost,nx});
            }
        }
    }
}

다익스트라 알고리즘과 경로를 추적하는 findParent 함수이다.

findParent함수는 재귀적으로 구성되어 있는데,
자신의 부모를 계속 호출하는 방식으로 재귀호출을 한다.

더 이상 부모가 없을 때까지
즉, 부모가 자기 자신을 가리키는 것을 찾을 때까지 반복한다.

parent [a] = b의 관계를 구성하는 것은 다익스트라 함수 안에서 해주는데,
d 배열을 갱신해 줄 때 같이 해준다.

핵심적인 함수에 대한 설명은 여기까지이고 이제 아래에 전체 코드에 대해 올리겠다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 9999999999

int n,m;
vector<pair<int,int>> v[1001];
long long d[1001] = {0,};
vector<int> path;
int parent[1001];
void findParent(int x){
    path.push_back(x);
    if(parent[x] == x) return;
    findParent(parent[x]);
}

// 다익스트라 알고리즘
void daijkstra(int num){
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q;
    d[num] = 0;
    q.push({0,num});
    while(!q.empty()){
        int x = q.top().second;
        long long cost = q.top().first;
        q.pop();
        for(int i = 0; i < v[x].size(); i++){
            int nx = v[x][i].first;
            long long nCost = v[x][i].second + cost;
            if(d[nx] > nCost){
                parent[nx] = x;
                d[nx] = nCost;
                q.push({nCost,nx});
            }
        }
    }
}

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> n >> m;
    
    for(int i = 0; i < m; i++){
        int v1, v2, v3;
        cin >> v1 >> v2 >> v3;
        bool flag = false;

        for(int i = 0; i < v[v1].size(); i++){
            //해당 출발지와 도착지와 동일한 입력이 들어왔다면
            if(v[v1][i].first == v2){
                flag = true;
                // 비용이 더 작은 것으로 갱신
                if(v[v1][i].second > v3) v[v1][i].second = v3;
                break;
            }
        }
        if(!flag) v[v1].push_back({v2,v3});
    }
    int start,end;
    fill(d,d+1001,INF);
    for(int i = 0; i <= n; i++) parent[i] = i;
    cin >> start >> end;
    daijkstra(start);
    findParent(end);
    reverse(path.begin(),path.end());
    cout << d[end] << "\n";
    cout << path.size() << "\n";
    for(auto it : path) cout << it << " ";
}

경로를 출력할 때 역순으로 되어있기 때문에, 벡터를 뒤집어야 원래 순서대로 된다.

---

시행착오

다익스트라 알고리즘까지는 쉽게 했는데, 경로 탐색에서 애를 먹었다.

처음에는 DFS를 이용해서 했다가 계속 틀렸다.
그다음에는 문제에 나와있지 않은 조건 때문에 고생했다.

저건 좀 억울하다. 스페셜 저지 문제는 저래도 되나? 잘 모르겠다.

경로 추적에 대해서 보긴 했는데, 실제로 활용해 보는 것은 이번이 처음이다.
여기서 경로 추적이 적용될 줄은 몰랐다. 

 

생활비..

https://toss.me/howudong

howudong님에게 보내주세요