[18352] 특정 거리의 도시 찾기 (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int>> A;
vector<int> cnt;
vector<int> visited;

void BFS(int node);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, k, x; cin >> n >> m >> k >> x;

    A.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        A[a].push_back(b);
    }

    visited.resize(n + 1);

    for (int i = 0; i <= n; i++)
        visited[i] = -1;

    BFS(x);

    for (int i = 0; i <= n; i++) {
        if (visited[i] == k) cnt.push_back(i);
    }

    if (cnt.empty()) cout << -1;
    else {
        sort(cnt.begin(), cnt.end());
        for (int i : cnt) cout << i << "\n";
    }
    
    return 0;
}

void BFS(int node) {
    visited[node]++;
    queue<int> Q;
    Q.push(node);

    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        
        for(int i : A[now]){
            if (visited[i] == -1) {
                visited[i] = visited[now] + 1;
                Q.push(i);
            }
        }
    }
}

 

BFS의 응용 문제

1. 2차원 vector A를 선언해 각 노드에 연결된 노드를 인접 리스트로 저장한다

2. 방문 여부를 체크하기 위한 vector visited와 최단 거리 k를 만족하는 노드를 저장하기 위한 vector cnt를 생성한다

3. 각 노드의 초기 visited 값을 -1로 설정하고, BFS 함수에 들어감과 동시에 0으로 만들어준다

=> 시작하는 노드(자기 자신)의 visted가 되어야 다음 노드로 넘어갈 때 1이 되어 1번 방문한 것이 되기 때문

4. BFS에서는 FIFO 방식으로 탐색하기 위해 queue를 사용한다

5. 현재 노드에서 인접한 모든 노드에 대해 visited의 값이 -1, 즉 방문하지 않았다면 queue에 삽입한다

6. 다시 main함수로 돌아가 최단 거리 k를 만족하는 노드의 vector cnt가 비어있다면 -1을 출력한다

7. cnt가 비어있지 않다면 오름차순으로 정리하여 최단 거리 k를 만족하는 노드를 모두 출력한다