Pythonで村の配水網を最適化する:Union-Findと最小全域木で最小コストを実現

問題の概要

ある村に n 軒の家があるとします。すべての家へ水を供給するためには、井戸を掘るか、パイプを敷設する必要があります。各家庭 i については、次の2つの選択肢があります。

• その家の中に井戸を建設する(費用は wells[i])
• 別の場所にある井戸からパイプで水を引く

家同士をパイプでつなぐ費用は配列 pipes で与えられ、pipes[i] は [house1, house2, cost] という形式で、house1 と house2 をつなぐパイプの敷設コストを表します。接続は双方向であることに注意してください。求めるのは、すべての家に水を供給するための最小総費用です。

入力例

n = 3、wells = [1,2,2]、pipes = [[1,2,1],[2,3,1]] の場合、出力は 3 になります。

上の図は、パイプで家同士をつなぐ際のコストを表しています。このケースでの最適な戦略は、1番目の家に費用1で井戸を建設し、残りの家を費用2でそこにつなぐことです。合計費用は 1 + 2 = 3 となります。

解決のアプローチ:仮想ノードと最小全域木(MST)

この問題を効率的に解く鍵は、「仮想ノード」という発想です。井戸の建設を、番号0の仮想的な水源ノードと各家をつなぐ辺とみなすことで、問題全体を最小全域木(Minimum Spanning Tree)の問題に変換できます。あとは Kruskal 法と Union-Find(素集合データ構造)を組み合わせて最小コストを求めます。

アルゴリズムの手順

1. find() 関数を定義します(引数:a)
   • parent[a] が -1 と等しければ、a を返します
   • parent[a] := find(parent[a])(経路圧縮)
   • parent[a] を返します
2. union() 関数を定義します(引数:a, b)
   • parent_a := find(a)、parent_b := find(b)
   • parent_a が parent_b と同じなら True を返します(すでに同一グループ)
   • parent[parent_b] := parent_a としてグループを統合し、False を返します
3. メイン処理
   • parent := サイズ n+1 のリストを作成し、すべて -1 で初期化
   • i を 0 から wells の長さまでループし、pipes の末尾に [0, i+1, well[i]] を追加(仮想ノード0と各家をつなぐ辺)
   • pipes 配列をコスト(第3要素)を基準にソート
   • cost := 0 とし、pipes 内の各辺について、union(source, destination) が False を返した場合(まだ未接続だった場合)のみ cost += temp を実行
   • cost を返します

Pythonでの実装例

class Solution(object):
   def find(self, a):
      if self.parent[a] == -1:
         return a
      self.parent[a] = self.find(self.parent[a])
      return self.parent[a]
   def union(self,a,b):
      parent_a = self.find(a)
      parent_b = self.find(b)
      if parent_a == parent_b:
         return True
      self.parent[parent_b] = parent_a
      return False
   def minCostToSupplyWater(self, n, well, pipes):
      self.parent = [-1 for i in range(n+1)]
      for i in range(len(well)):
         pipes.append([0,i+1,well[i]])
      pipes = sorted(pipes,key=lambda v:v[2])
      cost = 0
      for i in pipes:
         source = i[0]
         destination = i[1]
         temp = i[2]
         if not self.union(source,destination):
            cost+=temp
      return cost

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

入力

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

出力

3

まとめ

井戸の建設コストを「仮想ノード0からの辺」としてモデル化することで、一見複雑な配水最適化問題を標準的な最小全域木問題に落とし込めます。Kruskal 法の計算量は O(E log E)(E は辺の数)であり、Union-Find による経路圧縮を組み合わせることで、大規模な村でも高速に最小コストを求められます。グラフ理論の古典的テクニックが実務的なインフラ設計にも応用できる好例といえるでしょう。