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

최단 거리를 구하는 문제는 높은 확률로 BFS를 사용하면 된다.

위 그래프에서 1번 도시가 시작점이라고 가정하면, 0계층은 도시1, 1계층은 도시 2,3, 2계층은 도시 4인 트리로 볼 수 있다.

최단거리가 지정되어있으므로, 우리는 K-1 계층의 마을들을 찾으면 된다.

도로가 단방향으로 설정되어있기 때문에 그래프를 표현할때 행렬을 사용하는 것보다 인접 리스트, 즉 벡터를 사용하면 편하다.

 

<전체 코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
 
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int  N,M,K,X;
    cin>>N>>M>>K>>X;
    vector<vector<int>> v(N);
    queue<int> q;
    vector<int> his(N,-1);
 
    for(int t = 0; t<M; t++){
        int a,b;
        cin>>a>>b;
        v[a-1].push_back(b-1);
    }
 
    q.push(X-1);
    his[X-1] = 0;
    
    for(int t = 1; t<=K; t++){ // 거리 
        int qsize = q.size();
        while(qsize--){ // 계층에 있는 도시의 수만큼 돌면 됨
            int tem = q.front();
            q.pop();
            
            for(int i = 0; i<v[tem].size(); i++){
                int nxt = v[tem][i];
                if(his[nxt] != -1){ // 이미 방문 == 최단거리 아님
                    continue;
                }
                
                q.push(nxt);
                his[nxt] = t;
            }
        }
    }
    
    bool flg = false;
    for(int i = 0; i<N; i++){
        if(his[i] == K){
            flg = true;
            cout<<i+1<<endl;
        }
    }
    
    if(flg == false) cout<<-1<<endl;
    
 
}