백준 - 18352

 

문제링크

문제요약

단방향 그래프에서 시작지점 x를 주고 x에서 k만큼 떨어진 노드를 전부 출력하는 문제이다.

k까지의 최단거리를 찾는것이니 dfs를 돌린후 거리가 k만큼 나오는것을 출력하면된다.

 

문제자체가 DFS의 대표문제이니 수도코드나 해결법에대해 따로 적지는 않았다.

문제가 이해가 안간다면 dfs를 공부하고오는것이 좋다.

---

소스코드

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

/*
단방향 그래프가 주어질때 거리계산
bfs로 풀린텐데
시간 복잡도는 괜찮을지 의문
*/

vector<int> v[1000005];
int vist[300005] = {0,};
int n, m, k, x;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k >> x;
    for (int i = 0; i < m; i++) {
        int tmp, tmp1;
        cin >> tmp >> tmp1;
        v[tmp].push_back(tmp1);
    }

    queue<int> q;
    q.push(x);
    vist[x] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (const int e : v[cur]) {
            if (vist[e]) continue;
            q.push(e);
            vist[e] = vist[cur] + 1;
        }
    }

    int flag = 0;
    for (int i = 1; i <= n; i++) {
        if (vist[i] - 1 == k) {
            cout << i << "\n";
            flag = 1;
        }
    }
    if (!flag)
        cout << "-1";
}