🌳

[ARC031 B] 埋め立て

2024/02/26に公開

Ruby

いろんなアルゴリズムが学べる問題。

面倒な解法

地図を小さくして XOXO で考える
あらかじめ全体の O の数を数える → 2
- このあと X を一カ所 O にして全体が一つの大陸になるなら O の数は 3 になる
一つ目
- 一つ目の X の地点を O にする → OOXO
- その地点から繋がっている O を数える → 2
- 2 (繋がっている O の数) > 2 (全体の O の数) → false
二つ目
- 二つ目の X の地点を O にする → XOOO
- その地点から繋がっている O を数える → 3
- 3 (繋がっている O の数) > 2 (全体の O の数) → true

となって二つ目のケースで一つの島になるのがわかる。

地図	連結数	判定	結果
XOXO
OOXO	2	2 > 2	false
XOOO	3	3 > 2	true

同様に OXXO なら連結数は 2, 2 なので一つの大陸にはならない。

以上の考え方は深さ優先探索(DFS)または幅優先探索(BFS)で実装できる。

簡潔な解法

素集合森を使い、神視点で陸のセル同士を繋げていけば、それだけで「大陸の数」がわかる。DFS や BFS のように歩き回る必要はない。

DFS, BFS の実装をシンプルにする

一回の探索であれば地図を更新しても問題はない。しかし、この問題を解くには、最初から探索を繰り返すので、地図を更新してしまうと初期状態に戻すのが面倒になる。

そこで毎回、元の地図から探索用の地図にディープコピーする方法もあるが、そもそも元に戻すのが面倒なら地図に書き込まなければよい。

コード (AC)

共通前処理

W, H = 10, 10                       # => [10, 10]
A = H.times.collect { gets.strip }  # => ["xxxxxxxxxx", "xoooooooxx", "xxoooooxxx", "xxxoooxxxx", "xxxxoxxxxx", "xxxxxxxxxx", "xxxxoxxxxx", "xxxoooxxxx", "xxoooooxxx", "xxxxxxxxxx"]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def around_each
    AROUND.each do |e|
      v = self + e
      if Land[v]
        yield v
      end
    end
  end
end

AROUND = [V[0, -1], V[1, 0], V[0, 1], V[-1, 0]]

Land = {}
Sea = []
H.times do |y|
  W.times do |x|
    v = V[x, y]
    if A[y][x] == "o"
      Land[v] = true
    else
      Sea << v
    end
  end
end
Land.freeze

深さ優先探索 (126 ms)

def dfs(v, visited = {})
  count = 0
  unless visited[v]
    visited[v] = true
    count += 1
    v.around_each do |e|
      count += dfs(e, visited)
    end
  end
  count
end

ans = Sea.any? { |v| dfs(v) > Land.size }  # => true
puts ans ? "YES" : "NO"

再帰呼び出しが気になる場合はキューを使った幅優先探索のような書き方にも変更できる。

幅優先探索 (58 ms)

def bfs(v)
  queue = [v]
  count = 0
  visited = {}
  while v = queue.shift
    unless visited[v]
      visited[v] = true
      count += 1
      v.around_each { |e| queue << e }
    end
  end
  count
end

ans = Sea.any? { |v| bfs(v) > Land.size }  # => true
puts ans ? "YES" : "NO"

shift を pop に変更し、キューから直前の座標を取り出すように変更すると「再帰呼び出しを行わない深さ優先探索」になる。

素集合森 (246 ms)

def single_tree?(v)
  ds = DisjointSet.new
  [v, *Land.keys].each do |v|
    ds.make_set(v)
    v.around_each { |e| ds.unite(v, e) }
  end
  ds.tree_count == 1
end

ans = Sea.any? { |v| single_tree?(v) }  # => true
puts ans ? "YES" : "NO"

足跡用のバッファを別に用意する必要がなく、たんに「陸にしたい海の位置」と「既存の陸の位置」をまとめて素集合森を作るだけでよい。手続き型な書き方のため理解しやすい。