특정 거리의 도시 찾기 18352

문제

접근 방법

모든 도로의 거리는 1이기에 BFS를 활용하면 된다.
아무리 복잡한 그래프 관계일지라도 현재 지점에서 가까운 지점부터 방문하기에 현재 지점에서 다른 지점까지의 최소 거리로 갱신된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, K, X;
vector<int> ret, isVisited;
vector<vector<int>> graph;
queue<int> q;
void bfs()
{
    q.push(X);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int next : graph[cur])
        {
            if (isVisited[next] != -1)
                continue;
            isVisited[next] = isVisited[cur] + 1;
            q.push(next);
            if (isVisited[next] == K)
                ret.push_back(next);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> K >> X;
    graph = vector<vector<int>>(N + 1, vector<int>());
    isVisited = vector<int>(N + 1, -1);
    isVisited[X] = 0;
    while (M--)
    {
        int A, B;
        cin >> A >> B;
        graph[A].push_back(B);
    }
    bfs();
    if (ret.empty())
    {
        cout << -1;
        return 0;
    }
    sort(ret.begin(), ret.end());
    for (int i : ret)
        cout << i << "\n";
    return 0;
}

풀이

기초적인 BFS 문제이다.
응답에 사용될 도시의 번호는 벡터로 저장해 두었다가 정렬하면 된다.