[BOJ 18352] 특정 거리의 도시 찾기

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

 

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다 !!

문제에서 계속 언급한 것처럼 '최단 거리'를 구하는 문제이기 때문에 다익스트라 알고리즘 or 플로이드-와샬 알고리즘을 사용해야겠다고 생각할 수 있었다.

1. 출발 도시 번호가 주어지고 특정 노드로부터 다른 노드의 최단 거리를 구해야 함
2. 입력으로 주어지는 n, m, k가 각각 30만, 100만, 30만으로 작지 않음

1번만으로도 다익스트라 알고리즘으로 풀어야 한다는 것을 알 수 있지만, 입력으로 주어진 수들도 범위가 크기 때문에 귀찮다고 플로이드-와샬로 풀면 시간 초과가 난다는 것을 캐치할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

#define INF 9876543421

map<int, vector<int>> mp; // 인접 리스트
vector<int> dist; // 거리 정보
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, k, x; // 도시의 개수, 도로의 개수, 거리 정보, 출발 도시
    cin >> n >> m >> k >> x;

    int a, b;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        mp[a].push_back(b);
    }

    // 다익스트라 알고리즘을 수행
    // 초기 노드 삽입
    dist = vector<int>(n+1, INF);
    pq.push({0, x});
    dist[x] = 0;

    int d, now, cost;
    while (!pq.empty()) {
        d = pq.top().first;
        now = pq.top().second;
        pq.pop();

        if (dist[now] < d) continue;
        for (auto elem : mp[now]) {
            cost = d + 1;
            if (cost < dist[elem]) {
                dist[elem] = cost;
                pq.push({cost, elem});
            }
        }
    }

    vector<int> ret;
    for (int i = 1; i < dist.size(); ++i) {
        if (dist[i] == k) ret.push_back(i);
    }

    if (ret.empty()) cout << -1 << "\n";
    else {
        for (auto elem : ret) {
            cout << elem << "\n";
        }
    }

    return 0;
}