백준 18352번: 특정 거리의 도시 찾기

문제 링크 : https://www.acmicpc.net/problem/18352

참고한 블로그 :
https://yabmoons.tistory.com/364
https://code-lab1.tistory.com/29

그래프쪽 문제를 푸는데 다익스트라 알고리즘이 꽤 많이 나와서 이참에 공부를 하자 싶어서 쉬운 문제부터 풀기로 했다. 알고리즘 수업 때 그래프 탐색 방법으로 배우긴 했었는데 이름만 기억할 뿐 이미 다 잊어버렸었고, 그때도 이론만 배웠을 뿐 코드로 짜보는 것은 이번이 처음이었다.

• 다익스트라 알고리즘
  그래프에서 시작 노드가 주어질 때, 다른 모든 노드들까지의 최소 비용을 구하는데 적합한 알고리즘
  (단, 가중치가 음수인 경우에는 적용할 수 없다.)
  
  

• 알고리즘 동작 원리

1. 시작 노드와 직접적으로 연결된 노드들을 찾아서 거리를 갱신, 시작 노드를 방문한 노드로 체크한다.
2. 방문한 노드들과 연결된 노드들 중에서 비용이 가장 적은 노드를 선택해서 방문한 노드로 체크한다.
3. 2번 과정에서 갱신할 수 있는 노드의 비용을 갱신해준다.
4. 2 ~ 3번 과정을 반복한다.

배열을 이용해서 코딩을 하면 시간복잡도가 O(n²)이 나오게 되고 우선순위 큐를 이용하면 O(E * logN)로 줄일 수 있다고 한다.

문제 코드는 다익스트라 알고리즘 코드를 그대로 쓰고 아래에 출력 조건만 적어서 제출했다.

<작성한 코드>

#include <iostream>
#include <vector>
#include <queue>
#define INF 9999999
using namespace std;

int n, m, k, x;
vector<pair<int, int>> v[300001];

void dijkstra(){
    vector<int> dist(n + 1, INF); // 처음에 INF로 초기화
    priority_queue<pair<int, int>> pq; // (cost, cur)
    
    dist[x] = 0;
    pq.push({0, x});
    
    while(!pq.empty()){
        int cost = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < v[cur].size(); i++){
            int next = v[cur][i].first; // 다음 노드
            int ncost = cost + v[cur][i].second; // 다음 노드까지의 가중치
            
            if(ncost < dist[next]){ // 더 작은 값을 구한 경우
                dist[next] = ncost; // 값 갱신
                pq.push({-ncost, next}); // pq에 삽입
            }
        }
    }
    
    bool flag = true;
    for(int i = 1; i <= n; i++){
        if(dist[i] == k){
            flag = false;
            cout << i << endl;
        }
    }
    if(flag) // 최단거리가 k인 도시가 없는 경우 -1 출력
        cout << -1;
}

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &x);
    
    for(int i = 0; i < m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].push_back({y, 1}); // cost는 전부 1
    }

    dijkstra();
}