C++で解くバス路線問題：目的地までの最小乗車回数を求めるアルゴリズム

問題概要

バス路線のリストが与えられます。各 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 になります。これは、まず 1 台目のバスで乗り換え地点となるバス停 8 まで移動し、そこで 2 台目のバスに乗り換えてバス停 6 へ向かうためです。

解法のアプローチ

この問題は幅優先探索（BFS）を使うことで効率的に解けます。ポイントは、「バス停」ではなく「路線」単位で探索することです。同じ路線に乗り続けている間は乗車回数が増えないため、訪問済みの路線を管理しながら、乗車回数（レベル）ごとに探索範囲を広げていきます。

具体的な手順は以下の通りです。

• マップ m を定義する
• i := 0 として、i < r.size() の間 i を 1 ずつ増やしながら以下を繰り返す
  • j := 0 として、j < r[i].size() の間 j を 1 ずつ増やしながら以下を繰り返す
    • m[r[i][j]] の末尾に i（路線番号）を追加する
• キュー q を定義し、S を追加する
• S == T の場合は 0 を返す
• 集合 visited を定義する
• lvl := 1 として、q が空でない間 lvl を 1 ずつ増やしながら以下を繰り返す
  • sz := q.size()
  • sz が 0 でない間、以下を繰り返す
    • node := q.front() で先頭要素を取り出し、キューから削除する
    • i := 0 として、i < m[node].size() の間 i を 1 ずつ増やしながら以下を繰り返す
      • route := m[node][i]
      • route がすでに visited に含まれている場合は、処理をスキップして次へ進む
      • route を visited に追加する
      • j := 0 として、j < r[route].size() の間 j を 1 ずつ増やしながら以下を繰り返す
        • 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

出力

2

補足：計算量について

前処理で全バス停と路線の対応関係を構築するのに O(総バス停数)、BFS 本体では各路線を高々一度しか訪問しないため、全体の計算量は O(路線数 × 1路線あたりのバス停数) 程度に抑えられます。「乗車回数の最小化」という問題をグラフ探索に帰着させる、典型的な BFS の応用例といえるでしょう。