알고리즘 :: 백준 :: BFS :: 18352 :: 특정 거리의 도시 찾기

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.

문제접근

• 임의의 한 점에서 시작해서 다른 점까지의 최단 거리를 계산해야 하는 문제이므로 BFS를 사용해야 함을 알 수 있다.
• 임의의 한 점까지 이르는 최단 거리를 외부에 저장해야 한다.
  • 예를 들어, A->B->C 와 A->D->B->C 경로가 있다면, C에 2를 기록하는 것이 맞다.
• 모든 점에 대해서 최단 거리를 계산했다면, 외부에 기록했던 각 정점까지의 최단 거리를 순차탐색하면서 최단 거리가 K인 정점들을 뽑아낸다.

코드

// https://www.acmicpc.net/problem/18352
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

static int N, M, K, X, dist[300001];
static vector<int> city[300001];

void bfs() {
    memset(dist, -1, sizeof(dist));
    queue<pair<int, int>> q;
    q.push({X, 0});
    dist[X] = 0;

    while(!q.empty()) {
        int v = q.front().first, d = q.front().second; 
        q.pop();
        for (const int& i : city[v])
            if (dist[i] == -1) {    // 아직 방문하지 않은 정점이라면,
                q.push({i, d + 1}); // queue에 push 해주고,
                dist[i] = d + 1;    // 최단 거리를 기록한다.
                // Q. 왜 dist[i]를 최소값으로 갱신하기 위해 min()을 사용하지 않는가?
                // A. 시작지점에서 순서대로 방문하는 BFS 특성상, 먼저 방문하는 경우가 무조건 최소 길이다.
                //    A->C 보다 A->B->D->C 보다 짧은건 당연하다.
            }
    }
    vector<int> ret;
    for (int i = 1; i <= N; ++i)
        if (dist[i] == K) ret.push_back(i);
    if (ret.empty()) ret.push_back(-1);
    for (const int& i : ret) cout << i << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M >> K >> X;    // 도시의 개수, 도로의 개수, 거리, 출발 도시 번호
    for (int i = 0; i < M; ++i) {
        int s, e; cin >> s >> e;
        city[s].push_back(e);   // 단방향 그래프 간선 생성.
    }
    bfs();
}

결과