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

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

문제

한 방향 그래프가 주어지고,,
시작 노드가 주어진다..
특정 깊이에 존재하는 노드들을 출력하는 문제다.

 

 

풀이

1. 문제의 범위 조건을 잘 확인하자..
2. 정답 출력시 오름차순으로 출력해야한다. 역시 조건을 잘 확인하자..

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graph(300001);
int min_score = INT_MAX;
vector<int> ans_list;
int n;

void print_answer()
{
    sort(ans_list.begin(), ans_list.end());
    if (ans_list.size())
    {
        for (auto e : ans_list)
        {
            cout << e << endl;
        }
    }
    else
    {
        cout << -1;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 입력
    int m, k, x;
    cin >> n >> m >> k >> x;

    while (m--)
    {
        int s, e;
        cin >> s >> e;
        graph[s].push_back(e);
    }

    vector<bool> is_visited(n + 1, false);
    queue<pair<int, int>> q;
    q.push({x, 0}); // node_id, score;
    is_visited[x] = true;

    while (!q.empty())
    {
        auto [node_id, score] = q.front();
        q.pop();

        for (int next : graph[node_id])
        {
            if (!is_visited[next])
            {
                // 만약 방문하지 않았다면
                q.push({next, score + 1});
                is_visited[next] = true;
            }
        }

        if (score == k)
        {
            ans_list.push_back(node_id);
        }
        else if (score > k)
        {
            break;
        }
    }

    print_answer();
}