C++로 푸는 버스 노선 문제: BFS로 최소 탑승 버스 수 구하기

문제 개요

버스 노선 목록이 있다고 가정해 보겠습니다. 각 routes[i]에는 i번째 버스가 영원히 반복 운행하는 경로가 담겨 있습니다. 예를 들어 routes[0] = [1, 5, 7]이라면 0번 버스는 1 → 5 → 7 → 1 → 5 → 7 … 순서로 정류장을 무한히 순환한다는 의미입니다.

이제 우리는 어떤 버스도 타지 않은 상태에서 S 정류장에 서 있고, T 정류장으로 이동하려고 합니다. 목적지에 도착하기 위해 최소 몇 대의 버스를 타야 할까요? 만약 어떤 방법으로도 도달할 수 없다면 -1을 반환해야 합니다.

예를 들어 입력이 [[1,2,8],[3,6,8]]이고 S = 1, T = 6이라면 출력은 2입니다. 먼저 0번 버스를 타고 정류장 8까지 이동한 뒤, 같은 정류장에서 1번 버스로 갈아타 정류장 6에 도착하기 때문입니다.

풀이 접근 방식

이 문제는 너비 우선 탐색(BFS)으로 해결할 수 있습니다. 핵심은 개별 정류장이 아니라 노선(route) 단위로 탐색한다는 점입니다. 같은 노선에 속한 정류장들은 한 번의 탑승으로 모두 도달할 수 있기 때문입니다.

구체적인 단계는 다음과 같습니다.

정류장을 키(key)로, 해당 정류장을 지나는 버스 번호 목록을 값(value)으로 갖는 맵 m을 정의합니다.
i := 0부터 r의 크기 미만까지 반복하며, 각 i에 대해 j := 0부터 r[i]의 크기 미만까지 반복해서 m[r[i][j]]의 끝에 i를 추가합니다.
큐(queue) q를 정의하고 S를 삽입합니다.
S와 T가 같다면 탑승이 필요 없으므로 0을 반환합니다.
이미 확인한 노선을 기록할 집합(set) visited를 정의합니다.
lvl := 1부터 시작해 큐가 빌 때까지 반복하며, 매 반복마다 lvl을 1씩 증가시킵니다.
- sz := 큐의 현재 크기를 저장합니다.
- sz가 0이 될 때까지 다음을 반복합니다.
  - node := 큐의 맨 앞 요소를 꺼내고 큐에서 제거합니다.
  - i := 0부터 m[node]의 크기 미만까지 반복합니다.
    - route := m[node][i]
    - route가 이미 visited에 있다면 이후 과정을 생략하고 다음 반복으로 넘어갑니다.
    - route를 visited에 추가합니다.
    - j := 0부터 r[route]의 크기 미만까지 반복합니다.
      - stop := r[route][j]
      - stop이 T와 같다면 lvl을 반환합니다.
      - 그렇지 않으면 stop을 q에 삽입합니다.
  - sz를 1 감소시킵니다.
큐가 모두 비었는데도 목적지에 도달하지 못했다면 -1을 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numBusesToDestination(vector<vector<int>>& r, int S, int T) {
      unordered_map <int, vector <int> > m;
      for(int i = 0; i < r.size(); i++){
         for(int j = 0; j < r[i].size(); j++){
            m[r[i][j]].push_back(i);
         }
      }
      queue <int> q;
      q.push(S);
      if(S == T) return 0;
      unordered_set <int> visited;
      for(int lvl = 1; !q.empty(); lvl++){
         int sz = q.size();
         while(sz--){
            int node = q.front();
            q.pop();
            for(int i = 0; i < m[node].size(); i++){
               int route = m[node][i];
               if(visited.count(route)) continue;
               visited.insert(route);
               for(int j = 0; j < r[route].size(); j++){
                  int stop = r[route][j];
                  if(stop == T) return lvl;
                  q.push(stop);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,8}, {3,6,8}};
   cout << (ob.numBusesToDestination(v, 1, 6));
}

입력

{{1,2,8}, {3,6,8}}
1
6

출력

핵심 포인트

BFS의 레벨(level)이 곧 '지금까지 탑승한 버스의 수'를 의미합니다.
방문 체크를 정류장이 아니라 노선 단위로 수행하면 중복 탐색을 크게 줄여 효율을 높일 수 있습니다.
S == T인 경우는 버스를 탈 필요가 없으므로 즉시 0을 반환합니다.

복잡도 분석

시간 복잡도: 모든 노선과 정류장 조합을 최대 한 번씩만 처리하므로 O(N × K)입니다. 여기서 N은 노선의 수, K는 노선당 평균 정류장 수입니다.

공간 복잡도: 정류장-노선 맵, 큐, 방문 집합에 저장되는 데이터 양에 비례합니다.