99클럽 코테 스터디 10일차 TIL + BFS(C++)

문제

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

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

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> dist(300001, -1);  // -1로 초기화하여 방문하지 않음을 나타냄
vector<int> graph[300001];
int N, M, K, X, A, B;
bool found = false;

void bfs(int start) {
    dist[start] = 0;
    queue<int> q;
    q.push(start);

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

        for (int y : graph[x]) {
            if (dist[y] == -1) { // 아직 방문하지 않은 경우에만
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
    }    
}

int main() {
    cin >> N >> M >> K >> X;

    while (M--) {
        cin >> A >> B;
        graph[A].push_back(B);
    }

    for (int i = 0; i <= N; i++)
        sort(graph[i].begin(), graph[i].end());

    bfs(X);

    for (int i = 1; i <= N; i++) { 
        if (dist[i] == K) {
            found = true;
            cout << i << '\n';
        }
    }

    if (!found)
        cout << "-1";

    return 0;
}

 

풀이

최단 거리 문제 → BFS

• 이 문제는 방향이 있는 그래프이므로, 예제와 같이 graph에 노드를 저장했을 때 아래와 같은 인접 리스트가 형성된다.
  • [1]: 2, 3
  • [2]: 3
  • [3]: (없음)
  • [4]: (없음)
• 시작 노드 X부터 BFS를 실행해 X부터 각 노드까지의 최단거리를 dist 벡터에 저장한다. dist 배열의 인덱스는 노드의 번호, 배열의 원소는 시작 노드 X에서부터 해당 노드까지의 최단 거리를 의미한다.
• BFS로 노드들을 재귀적으로 탐색할 때, 방문하지 않은 노드인 경우 dist[y] = dist[x] + 1;로 이전 노드까지의 최단거리에 1을 더해 현재 노드까지의 최단 거리를 저장한 후, 현재 노드를 큐에 집어넣는다.
• BFS 실행이 끝나면 dist 배열을 순회하며 K와 같은 값을 가지는 dist 배열의 인덱스, 즉 노드의 번호를 출력한다.
• 이때, K와 같은 최단거리를 가지는 노드가 없을 때는 -1을 출력해야 하므로, dist 배열 순회시 K와 같은 dist[i]를 찾으면 boolean 타입의 플래그 변수 found를 true로 설정한다. 마지막에 found가 false라면 -1를 출력한다.