(매일 BOJ) C++ 18352번 특정 거리의 도시 찾기

이번 문제는 18352번 특정 거리의 도시 찾기이다

문제 요약

• 입력
  • N(도시 수), M(도로 수), K(목표 거리), X(시작 도시)
  • M개의 도로: a -> b (단방향)
• 출력
  • X로부터 최단거리가 정확히 K인 도시 번호들을 오름차순으로 출력
  • 없다면 -1

접근 아이디어

• dist[v] = 시작점 X에서 v까지의 최단거리를 저장하는 BFS를 수행
• 방문하지 않았던 정점만 방문(dist == -1)
• 거리 갱신 직후 dist[next] == K이면 answer에 담아둔 후 최종적으로 answer를 정렬해 출력하면 끝

작성코드

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


int N,M,K,X;
void BFS(vector<vector<int>> & city,vector<int> & answer);
int main (void){
    cin >> N >> M >> K >> X;
    vector<vector<int>> city(N+1);
    for(int i = 1; i <= M; i++){
        int a,b;
        cin >> a >> b;
        city[a].push_back(b);
    }

    vector<int> answer;
    BFS(city,answer);
    sort(answer.begin(),answer.end());
    
    if(answer.empty()) {
        cout << -1 << '\n';
        return 0;
    }

    else{
        for(int i : answer){
            cout << i << '\n';
        }
        return 0;
    }
}

void BFS(vector<vector<int>> & city,vector<int> & answer){
    vector<int> distance(N+1,-1);
    queue<int> q;
    q.push(X);
    distance[X] = 0;

    while(!q.empty()){
        int current = q.front();
        q.pop();

        for(int next : city[current]){
            if(distance[next] == -1){
                q.push(next);
                distance[next] = distance[current] + 1;
                if(distance[next] == K) answer.push_back(next);
            }
        }
    }
}