[Algorithm]Baekjoon 18352번 :: 특정 거리의 도시 찾기

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

18352번: 특정 거리의 도시 찾기

int n, m, k, x, a, b;
vector<vector<int>> graph(300001);
int dist[300001];
vector<int> answers;
 
void BFS()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[x] = 0;
 
    queue<int> q;
    q.push(x);
 
    while (!q.empty())
    {
        int curNode = q.front();
        q.pop();
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i];
 
            if (dist[nextNode] == 0x3f3f3f3f)
            {
                dist[nextNode] = dist[curNode] + 1;
                q.push(nextNode);
 
                if (dist[nextNode] == k) answers.push_back(nextNode);
            }
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> k >> x;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        graph[a].push_back(b);
    }
 
    BFS();
 
    if (answers.size() == 0) printf("%d", -1);
    else
    {
        sort(answers.begin(), answers.end());
        for (int i = 0; i < answers.size(); ++i) printf("%d\n", answers[i]);
    }
}

요구하는 숫자와 일치하는 최단거리의 도시들을 구하는 문제인데... 사실 그냥 기본적인 BFS구현할 줄 알면 된다.

생각보다 정답률이 낮길래 무슨 함정이 있나? 했지만 그런건 딱히 없다.

간선의 가중치는 1로 고정이기 때문에, BFS 수행 시 처음 만났을 때가 무조건 최단거리임이 보장된다.

만약 가중치가 제각각이였다면 다익스트라를 사용하면 된다.