특정 거리의 도시 찾기 (feat. 백준, 18352번)

특정 거리의 도시 찾기
https://www.acmicpc.net/problem/18352

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

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <queue>
using namespace std;
int check[300001];
set<int> arr[300001], ans;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, K, X;
    cin >> N >> M >> K >> X;
    for(register int m = 0, A, B; m < M; ++m)
        cin >> A >> B, arr[A].insert(B);
    for(register int n = 0; n <= N; ++n)
        check[n] = -1;
    queue<int> q;
    q.push(X);
    check[X] = 0;
    while(!q.empty()){
        auto p = q.front(); q.pop();
        if(check[p] > K)
            continue;
        if(check[p] == K)
            ans.insert(p);
        for(auto iter = arr[p].begin(); iter != arr[p].end(); ++iter)
            if(check[*iter] == -1)
                check[*iter] = check[p] + 1, q.push(*iter);
    }
    if(ans.empty())
        cout << -1;
    else
        for(auto& v : ans)
            cout << v << "\n";
    return 0;
}
// *&)*@*

 

반응형

1. 단방향이라는 점과 시작지점이 주어진다는 것에 주의해야 합니다. 또한 다익스트라의 기본 형태이므로 꼭 코드를 통해 생각을 정리할 필요가 있습니다.
2. X = 1, 1->2, 1->3이 있다면 1이라는 위치는 0을, 2와 3이라는 위치는 1의 위치 + 1을 해주면 되겠습니다. 즉 P = X + 1 의 형태입니다.
3. 결과적으로 P == K인 경우를 모두 구해주게 됩니다.
   다만, P > K 조건인 경우 정답을 벗어나는 경우이므로 continue한다면 수행 시간이 좀 더 빨라질 수 있습니다.