[BOJ알고리즘, C++]#18352_특정 거리의 도시 찾기, 최단 경로 알고리즘, BFS

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. BFS 최단 경로

[알고리즘]#2_길 찾기 알고리즘

 

[정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 알고리즘입니다. BFS는 가중치가 없거나 혹은 일정한 경우 그래프의 최단 경로 탐색을 위해 사용할 수 있습니다.

[특징] : 큐 활용

 

2. set 컨테이너

[Basic C++] #29_Set, STL 컨테이너

 

[정의] : C++의 STL에서 제공하는 set 컨테이너는 노드 기반의 연관 컨테이너로, Key 값을 원소로 균형 이진트리 자료구조에 저장하는 컨테이너입니다.

[특징] : set 컨테이너는 중복을 허용하지 않으며, 내부적으로 반 정렬된 상태를 유지합니다.

 

3. BFS로 최단 경로 찾고, 최단 경로가 K인 정점의 번호를 set에 삽입!

 

1. 먼저, BFS를 통해 각 정점의 최단 경로 값을 찾습니다.
2. 그리고, 최단 경로 값이 K인 정점을 set 컨테이너에 삽입합니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>
using namespace std;

int N, M, K, X;
vector<vector<int>> graph;
set<int> s;
vector<int> dist;

void bfs()
{
    vector<bool> visited(N + 1, false);
    queue<int> q;

    dist[X] = 0;
    q.push(X);
    visited[X] = true;

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

        for (const auto &neighbor : graph[cur])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                q.push(neighbor);
                dist[neighbor] = dist[cur] + 1;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> K >> X;

    graph.resize(N + 1);
    dist.resize(N + 1, 0);

    while (M--)
    {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
    }

    // BFS 수행
    bfs();

    for (int i = 1; i <= N; ++i)
    {
        if (dist[i] == K)
            s.insert(i);
    }

    // 결과 출력
    if (s.empty())
    {
        cout << -1;
    }
    else
    {
        for (auto it = begin(s); it != end(s); ++it)
            cout << *it << '\n';
    }

    return 0;
}

 

---