[BOJ 백준] 18352번 특정 거리의 도시 찾기

문제

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

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

접근

 BFS를 이용해 풀 수 있는 간단한 문제이다. queue에 값을 넣을 때마다 깊이를 체크해주며 깊이가 K라면 정답을 출력할 배열에 넣어주면 된다. 즉, 기존의 BFS를 구현하는 코드에서 if문 하나만 추가해주면 되는 것이다. 나는 이 과정에서 자동으로 오름차순 정렬을 위해 set을 사용하였으나 vector와 sort를 사용해줘도 상관없다.

코드

#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define endl "\n"

using namespace std;

int N, M, K, X, visit[300010] = {0};
vector<int> map[300010];
set<int> ans;

int main() {
    cin >> N >> M >> K >> X;
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        map[a].push_back(b);
    }

    queue<pair<int, int>> q;
    q.push({X, 0});
    visit[X] = 1;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        if (p.second > K)
            break;
        for (int i = 0; i < map[p.first].size(); i++) {
            if (visit[map[p.first][i]] != 0)
                continue;
            if (p.second + 1 == K)
                ans.insert(map[p.first][i]);
            q.push({map[p.first][i], p.second + 1});
            visit[map[p.first][i]] = 1;
        }
    }
    if (ans.size() == 0)
        cout << -1;
    else {
        for (auto i : ans)
            cout << i << endl;
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study