Pythonで解く並行コース問題 ― BFSで全コース修了に必要な最小学期数を求める

問題の概要

N個のコースがあり、それぞれ1からNまでの番号が付けられています。さらに、前提関係を表す配列 relations が与えられ、relations[i] = [X, Y] は「コースXはコースYの前提科目である」ことを意味します。つまり、コースYを受講する前に、必ずコースXを修了しておかなければなりません。

1つの学期では、受講したいコースの前提科目がすべて修了済みであれば、何コースでも同時に履修できます。このとき、すべてのコースを修了するために必要な最小の学期数を求めてください。なお、前提関係に循環が含まれるなどして、すべてのコースを修了できない場合は -1 を返します。

入力例

N = 3、relations = [[1,3],[2,3]] の場合を考えてみましょう。

• 1学期目：コース1とコース2を履修（どちらにも前提科目がないため）
• 2学期目：コース3を履修（前提科目である1と2が修了済みのため）

したがって、この場合の出力は 2 となります。

解法のアプローチ

この問題は、グラフ理論におけるトポロジカルソートの考え方と幅優先探索（BFS）を組み合わせることで効率的に解けます。各学期で「今すぐ履修できるコース」（＝前提科目がすべて修了済み、つまり入次数が0のコース）を一括して処理し、それを1学期として数えていくイメージです。

アルゴリズムの手順

1. courses を n で初期化します。
2. サイズ n+1 の配列 visited を作成し、すべて false で埋めます。
3. 空のキュー queue を用意します。
4. n+1 個の空リストからなる隣接リスト graph を作成します。
5. サイズ n+1 の配列 in_degree を作成し、すべて 0 で埋めます。
6. relations の各要素 i について、次の処理を行います。
   • graph[i[0]] の末尾に i[1] を追加します。
   • in_degree[i[1]] を 1 増やします。
7. 入次数が 0 のコース（前提科目がないコース）をすべてキューに追加し、visited を true にします。
8. semester を 1 に設定し、courses からキューのサイズを引きます（これらのコースは1学期目に履修完了となるためです）。
9. キューが空でなく、かつ未履修のコースが残っている間、次を繰り返します。
   • 現在のキューのサイズを current_size として記録します。
   • current_size 回だけ次を繰り返します。
     • キューの先頭からコースを取り出します。
     • そのコースを前提とする各コースについて、in_degree を 1 減らします。
     • 対象コースが未訪問で in_degree が 0 になったら、courses を 1 減らし、キューに追加して visited を true にします。
   • 1レベル（1学期分）の処理が終わったら、semester を 1 増やします。
10. 最後に、courses が 0 なら semester を返し、そうでなければ -1 を返します。循環が存在する場合、一部のコースは永遠に履修条件を満たせないため、-1 が返される仕組みです。

Pythonでの実装例

class Solution(object):
    def minimumSemesters(self, n, relations):
        courses = n
        visited = [False] * (n + 1)
        queue = []
        graph = [[] for _ in range(n + 1)]
        in_degree = [0] * (n + 1)

        # グラフの構築と入次数のカウント
        for prev, nxt in relations:
            graph[prev].append(nxt)
            in_degree[nxt] += 1

        # 前提科目がないコース（入次数0）をキューへ
        for i in range(1, n + 1):
            if in_degree[i] == 0:
                queue.append(i)
                visited[i] = True

        semester = 1
        courses -= len(queue)  # 1学期目に履修できるコース数を差し引く

        # BFSで学期（レベル）ごとに処理
        while queue and courses:
            current_size = len(queue)
            while current_size:
                current_course = queue.pop(0)
                current_size -= 1
                for nxt in graph[current_course]:
                    in_degree[nxt] -= 1
                    if not visited[nxt] and in_degree[nxt] == 0:
                        courses -= 1
                        queue.append(nxt)
                        visited[nxt] = True
            semester += 1

        return semester if courses == 0 else -1


ob = Solution()
print(ob.minimumSemesters(3, [[1, 3], [2, 3]]))

入力

3, [[1,3],[2,3]]

出力

2

計算量の評価

• 時間計算量：O(V + E)
  各コース（頂点）と各前提関係（辺）をそれぞれ高々1回しか処理しないためです。
• 空間計算量：O(V + E)
  隣接リスト・入次数配列・キューの保持に必要なメモリに依存します。

まとめ

前提関係を有向グラフとして捉え、入次数が0のコースを学期ごとにまとめて履修していくことで、必要な最小学期数を効率よく求められます。処理を進めても新たに履修可能なコースが現れなくなったのに未履修のコースが残っている場合は、前提関係に循環が存在することを意味するため、-1 を返すのがポイントです。