문제 1916. 최소비용 구하기(에센셜 4)

문제 링크

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

난이도 : Gold 5

 

문제 요약 설명

N개의 정점(도시)과 비용을 가지는 M개의 간선(버스)으로 이루어진 무방향 그래프가 있다. 정점 A에서 정점 B로 가는 최소비용을 구하는 프로그램을 작성해라.

입력

• 첫째 줄: 도시의 개수 N
• 둘째 줄: 버스의 개수 M
• 이후 M개의 줄 : 출발 도시 번호, 도착 도시 번호, 버스 비용
• 마지막 줄: 구하고자 하는 출발점의 도시번호, 도착점의 도시번호

입력 제한

• 도시의 개수 N(1 ≤ N ≤ 1,000)
• 버스의 개수 M(1 ≤ M ≤ 100,000)
• 0<= 버스 비용 < 100,000
• 출발점에서 도착점으로 갈 수 있는 경우만 입력으로 주어진다.

입력 예제

// input
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

// ans
4

 

풀이 방식

유사 다익스트라 알고리즘으로 풀었다. 이 문제를 풀 당시에 다익스트라 알고리즘이 익숙치 않아 머리 속에 떠오르는 알고리즘으로 작성했다. 부분 최소 비용이 발생할 때마다 큐에 저장하고 다시 큐에 꺼내서 최소 비용이 발생하는 지 확인하고... 반복하며 더이상 최소 비용이 발생하지 않을 때까지 반복하다 while문을 나가 결과를 출력했다.

 

정답 코드 

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAXN 1000000000
using namespace std;

struct pos_data_1916
{
    int pos;
    int distance;
};

int main() {
	fastio;
    int n, m; cin >> n >> m;

    vector<vector<int>> matrix;
    vector<int> shortest_path;
 
    matrix.resize(n+1, vector<int>(n+1, MAXN));
    shortest_path.resize(n+1);
  
    // input data
    int src, dst, w;
    for(int i = 0; i < m; i++){
        cin >> src >> dst >> w;
        // 출발지와 목적지가 같다면 작은값만 저장.
        matrix[src][dst] = min(matrix[src][dst], w);
    }

    int start, end; 
    cin >> start >> end;

    shortest_path = matrix[start];
    
    queue<pos_data_1916> q;

    // 시작 지점에서 각 정점까지의 거리를 q에 저장.
    for(int i = 1; i <= n; i++){
        q.push({i, shortest_path[i]});
    }

    while(!q.empty()){
        pos_data_1916 cur_pos = q.front(); q.pop();

        for(int i = 1; i <= n; i++){
            // start~cur_pos + cur_pos~i 까지의 거리가 저장된 start~i보다 짧다면,
            // 해당 거리를 shortest_path에 저장하고 q에도 저장.
            if(cur_pos.distance + matrix[cur_pos.pos][i] < shortest_path[i]){
                shortest_path[i] = cur_pos.distance + matrix[cur_pos.pos][i];
                q.push({i, cur_pos.distance + matrix[cur_pos.pos][i]});
            }
        }
    }
    
    cout << shortest_path[end] << '\n';

}

 

더 좋은 코드?

 

그래프에서 출발지와 도착지가 정해져있을 때 최단경로를 구하는 다익스트라 알고리즘이 있다. 다익스트라 알고리즘을 보다 정확히 적용하면 더욱 깔끔하고 좋은 코드가 나올 것으로 보인다.