[백준/C++] 18352 특정거리의 도시 찾기

백준

---

🤔문제 이해

최단거리로 도달할 수 있는 도시들 중 최단거리가 k인 경우만 출력해주는 문제이다.

---

💡첫번째 아이디어

다익스트라 문제인데 그냥 다익스트라를 수행한 후 최단 거리가 k인 값만 출력해주면 된다고 생각했다.

 

🔥풀이🔥

다익스트라 수행 후 dist[i]값이 k인 i만 출력

 

❌트러블 슈팅

dist를 모두 INF를 바꿔주고 시작점인 x만 0으로 바꿔주는 코드가 없어서 첫 제출에서 틀렸다.

dist[x] =0 코드 추가 후 제대로 돌아갔다.

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
#define INF 987654321

int n, m, k, x;
vector<vector<int>> edge;
int dist[300002];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k >> x;
    edge.resize(n + 1);
    int a, b;

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

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[x] = 0; //해당 코드 누락으로 86%에서 틀림

    priority_queue<pair<int, int>> pq;
    pq.push({0, x});

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (dist[now] < cost) continue;

        for (auto u: edge[now]) {
            int next_cost = cost + 1;

            if (dist[u] <= next_cost) continue;
            dist[u] = next_cost;
            pq.push({-(next_cost), u});
        }
    }
    int flag = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == k) {
            cout << i << "\n";
            flag = 1;
        }
    }
    if (flag == 0) cout << -1;

}

 

🔗참고할 문제

 

[백준/C++] 1753번 최단경로