プリム法で全部の倉庫を道でつなぐいちばん安い費用を求める

平面に散らばった倉庫を、碁盤の目の道でつないで、どの 2 つも行き来できるようにするいちばん安い費用を求めます。つないだまとまりから最も近い倉庫を 1 つずつ足していく、最小全域木のプリム法の練習です。

海外で定番の問題リスト 4 本には入っていません

問題

碁盤の目の町に、倉庫が散らばっています。倉庫の場所を、点 [x, y] の並び points で受け取ります。2 つの倉庫 [x1, y1] と [x2, y2] を道で結ぶ費用は、碁盤の目に沿った距離 |x1 - x2| + |y1 - y2| です。

何本かの道を作って、どの 2 つの倉庫のあいだも (ほかの倉庫を通ってもよいので) 行き来できるようにします。かかる費用の合計のいちばん安い値を返す関数を書いてください。

道は、倉庫と倉庫を直接結ぶ物だけを作れます
points の長さは 1 以上 1000 以下、x と y はどれも -1000000 以上 1000000 以下の整数で、同じ場所の倉庫はありません
倉庫が 1 つなら、道は要らないので 0 を返します

入力と出力の例

例 1

[0, 0] と [1, 3] を 4、[0, 0] と [4, 1] を 5、[4, 1] と [5, 5] を 5 で結ぶと、合計 14 で全部がつながります。

points = [[0, 0], [1, 3], [4, 1], [5, 5]]

例 2

一列に並んだ倉庫は、隣どうしを結ぶのがいちばん安く、3 + 2 + 4 で 9 です。

points = [[0, 0], [3, 0], [5, 0], [9, 0]]

例 3

倉庫が 1 つです。

points = [[-7, 2]]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「平面の点を全部つなぐ最小の費用を返してください。2 点の費用はマンハッタン距離です」
書き終えると「クラスカル法とプリム法のどちらを選びましたか？この問題ではなぜそちらですか？」と聞かれます
「全部の点の組が辺になるとき、辺の数はいくつですか？」と、辺の多いグラフでの計算量を聞かれます

道が直接結ぶ物だけか、点の数がどれくらいかを最初に確かめておくと、どの書き方が間に合うかが決まります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。

グラフ探索は、つながりを近い順か奥からたどります。迷路、最短の手数、講座を受ける順のような問題が同じ形です。

まず考える手順

段 1

倉庫を点、作れる道を線と見ると、全部の点をつなぐ線の組のうち、重さの合計がいちばん小さい物 (最小全域木) を求める問題です。どの 2 つの倉庫のあいだにも道を作れるので、線は n × (n - 1) ÷ 2 本あり、n が 1000 なら約 50 万本です。

段 2

プリム法を使います。1 つの倉庫から始め、「つないだまとまり」と「まだの倉庫」を結ぶ道のうち、いちばん安い道を作って、その倉庫をまとまりに足します。これを全部がつながるまで繰り返します。まとまりの外へ出るいちばん安い道は、どこかで必ず作ることになる道なので、先に作っても損をしません。

段 3

まだの倉庫ごとに、「まとまりまでのいちばん安い費用」を並びに持ちます。毎回、その値がいちばん小さい倉庫を選んで足し、足した倉庫からの費用で、まだの倉庫の値を小さく書き換えます。選ぶのも書き換えるのも O(n) なので、全体で O(n²) です。線が約 50 万本ある問題では、線を全部並べ替えるクラスカル法 (O(n² log n)) や、ヒープを使うプリム法より、この形が素直で速く済みます。

段 4

始めは 0 番の倉庫をまとまりにして、ほかの倉庫の値を 0 番からの費用にします。n - 1 回選んで足せば、全部がつながります。倉庫が 1 つなら、1 回も選ばずに 0 を返します。

解答

Python

def min_cost_connect(points):
    n = len(points)
    # まとまりまでの安い費用
    best = gaps(points, 0)
    done = [False] * n
    done[0] = True
    total = 0
    for _ in range(n - 1):
        v = pick(best, done)
        done[v] = True
        total += best[v]
        row = gaps(points, v)
        for u in range(n):
            if row[u] < best[u]:
                best[u] = row[u]
    return total


def gaps(points, v):
    # v からほかの倉庫への費用
    x, y = points[v]
    out = []
    for p, q in points:
        dx = abs(x - p)
        dy = abs(y - q)
        out.append(dx + dy)
    return out


def pick(best, done):
    # まだの中で最も安い倉庫
    v = -1
    for i in range(len(best)):
        if done[i]:
            continue
        if v == -1:
            v = i
        elif best[i] < best[v]:
            v = i
    return v

JavaScript

function minCostConnect(
  points,
) {
  const n = points.length;
  // まとまりまでの安い費用
  const best = points.map(
    (p) => cost(points[0], p));
  const done = best.map(
    () => false);
  done[0] = true;
  let total = 0;
  for (let k = 1; k < n; k++) {
    const v = pick(best, done);
    done[v] = true;
    total += best[v];
    const pv = points[v];
    points.forEach((p, u) => {
      const c = cost(pv, p);
      if (c < best[u]) {
        best[u] = c;
      }
    });
  }
  return total;
}

function cost(a, b) {
  return Math.abs(a[0] - b[0]) +
    Math.abs(a[1] - b[1]);
}

// まだの中で最も安い倉庫
function pick(best, done) {
  let v = -1;
  best.forEach((b, i) => {
    if (done[i]) {
      return;
    }
    if (v === -1 ||
      b < best[v]) {
      v = i;
    }
  });
  return v;
}

Go

func minCostConnect(
	points [][]int,
) int {
	n := len(points)
	cost := func(a, b int) int {
		p, q := points[a], points[b]
		return abs(p[0]-q[0]) +
			abs(p[1]-q[1])
	}
	// まとまりまでの安い費用
	best := make([]int, n)
	for i := range best {
		best[i] = cost(0, i)
	}
	done := make([]bool, n)
	done[0] = true
	total := 0
	for k := 1; k < n; k++ {
		v := -1
		for i := 0; i < n; i++ {
			if done[i] {
				continue
			}
			if v == -1 ||
				best[i] < best[v] {
				v = i
			}
		}
		done[v] = true
		total += best[v]
		for u := 0; u < n; u++ {
			best[u] = min(
				best[u], cost(v, u))
		}
	}
	return total
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

つないだ倉庫の値も書き換えていますが、つないだ倉庫は二度と選ばないので、答えには響きません。そのぶん、書き換えの所で「まだか」を確かめずに済みます。

計算量

時間は O(n²) です。n - 1 回の繰り返しのそれぞれで、いちばん安い倉庫を選ぶのと、値を書き換えるのが O(n) です
使う記憶は O(n) です。倉庫ごとの値と、つないだかどうかの印です

よくある間違い

全部の道を並べ替える。約 50 万本を並べ替えるクラスカル法でも解けますが、O(n² log n) の時間と O(n²) の記憶を使います。点どうしの全部が線になる問題では、並びで持つプリム法が速く、記憶も少なく済みます
いちばん近い倉庫どうしを順につなぐ。「いま見ている倉庫からいちばん近い倉庫」へ進むと、まとまり全体から見て安い道を見落とし、合計が高くなります。比べるのは、まとまり全体からの費用です
まっすぐの距離 (平方根) を使う。費用は碁盤の目に沿った距離です。例 1 で [0, 0] と [1, 3] は 4 です
倉庫が 1 つのときに困る。繰り返しが 0 回になるように書けば、そのまま 0 を返せます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def min_cost_connect(points: list[list[int]]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(min_cost_connect([[0, 0], [1, 3], [4, 1], [5, 5]]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します