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

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

1. 문제 이해

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어짐.

둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 주어짐( = A에서 B도시 이동하는 도로 존재 )

X로부터 출발하여 도달할 수 있는 도시 중 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력.

최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력.

 

2. 조건

- 모든 도로의 거리는 1

- 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력

 

3. 풀이

전형적인 BFS 문제라고 생각했다.

정답을 오름차순으로 출력해야했기 때문에 priority_queue를 사용했다.

#include <iostream>
#include <queue>
using namespace std;

#define MAX 300002
vector<int> graph[MAX];
queue<int> Q;
priority_queue<int, vector<int>, greater<>> pq;
int dist[MAX];
int n, m, k, v;
int a, b;

void BFS(int V) {
    Q.push(V);

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (int i = 0; i < graph[x].size(); i++) {
            int next = graph[x][i];

            if (next == V) {
                continue;
            }
            if (dist[next] == 0) { //visit 역할
                dist[next] = dist[x] + 1;
                Q.push(next);
            }
        }
    }
}

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

    cin >> n >> m >> k >> v;

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

    for (int i = 1; i <= n; i++) {
        if (dist[i] == k) {
            pq.push(i);
        }
    }

    if (pq.empty()) {
        cout << "-1";
    } else {
        while (!pq.empty()) {
            cout << pq.top() << "\n";
            pq.pop();
        }
    }

    return 0;
}

4. 반례

4 5 3 1
1 2
1 3
2 3
2 4
4 1

정답은 -1 이여야 하는데 1로 나옴 ...!

if(next == V)

     continue; 

추가해주었다.