백준 1916 <최소비용 구하기> C++ 풀이

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

1916번: 최소비용 구하기

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

 

#

 

요근래 계속 프로그래머스 문제만 풀었기때문에, 백준에서 문제를 풀어봤습니다.

백준과 프로그래머스 두 플랫폼은 문제의 느낌이 서로 다릅니다. 프로그래머스의 문제들이 좀 더 코딩테스트에 나오는 문제들과 결이 비슷하다면, 백준의 문제들은 기본기를 기르기에 좋은 문제들인것 같습니다(저의 주관적인 의견입니다!).

결과적으로 보면 코딩테스트에서 고득점을 받기 위해서는 두 플랫폼의 문제들을 골고루 다 푸는게 좋을것 같다는 생각이 들어, 앞으로는 번갈아가며 풀어보려고 합니다.

 

한 정점에서 다른 정점까지 가는 최단거리를 보고 다익스트라 알고리즘으로 문제를 풀어야겠다고 생각했습니다. 알고리즘을 외우기보단 이해하려고 노력했었던 덕에, 오랜만에 구현해봐도 한번에 잘 구현할 수 있었습니다. 평소대로라면 한번에 통과를 했어야하는데, 시간초과가 났습니다. endl이 들어가는 것도 아니었고 하다보니 알고리즘 내에서 시간을 오래 잡아먹는 요인이 있을거라 생각했습니다.

 

직접 break point를 걸어놓고 VS로 디버깅을 해보면서 문제점을 발견했습니다. 우선순위 큐에 같은 정점의 값이 여러개 들어가고 그 정점마다 계속 반복해서 for문을 도는데, 굳이 현재 정점의 최단거리보다 큰 거리값을 가진 큐는 for문을 돌필요가 없다는것을 깨달았습니다. 그래서 그 부분을 수정하고 채점을 받으니 통과할 수 있었습니다!

 

#

문제풀이 과정

1. 거리값을 저장할 dist 배열 생성 및 초기화(Init 함수)

2. 인접리스트를 통해 정점과 거리값 저장(adj 벡터)

3. dijkstra함수에 시작점과 도착점 그리고 adj 벡터 참조형식으로 전달

4. 다익스트라 알고리즘 수행

5. dist[도착정점] 값 출력

 

 

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
int N, M;
int dist[1001];
 
struct Node
{
    int node;
    int dist;
    Node(int a, int b)
    {
        node = a;
        dist = b;
    }
    bool operator<(const Node& other) const
    {
        return dist > other.dist;
    }
};
 
void Init()
{
    for (int i = 1; i <= N; i++)
    {
        dist[i] = INT_MAX;
    }
}
 
void dijkstra(int s, int e, vector<vector<pair<int, int>>>& adj)
{
    dist[s] = 0;
    priority_queue<Node> pq;
    pq.push(Node(s, 0));
 
    while (pq.empty() == false)
    {
        Node cur = pq.top();
        pq.pop();
        if (dist[cur.node] < cur.dist)
            continue;
 
        for (int i = 0; i < adj[cur.node].size(); i++)
        {
            int nextNode = adj[cur.node][i].first;
            int nextDist = adj[cur.node][i].second + cur.dist;
 
            if (dist[nextNode] > nextDist)
            {
                dist[nextNode] = nextDist;
                pq.push(Node(nextNode, nextDist));
            }
        }
    }
 
}
 
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> N >> M;
 
    Init();
    
    vector<vector<pair<int,int>>> adj(N+1);
 
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ b,c });        
    }
 
    int start, end;
    cin >> start >> end;
 
    dijkstra(start, end, adj);
 
    cout << dist[end];
}