めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

043 - Maze Challenge with Lack of Sleep(★4)の解説

何の話かと言うと

atcoder.jp

この問題をネタに「重み0のリンクで結合されたノードを同一視する」という話をします。

一般的な解法

まず、この問題の一般的な解法は、01-BFS になります。

方向転換を考慮する必要があるので、座標 (x, y) + 方向(上下方向 or 左右方向)をノードとします。たとえば、

・(1, 1, '|') : 座標 (1, 1) を上下方向に移動中
・(1, 1, '-') : 座標 (1, 1) を左右方向に移動中

という感じです。そして、これらのノードをリンクで結合します。

座標を変えずに方向だけ変えるリンクを重み 1 とします。

・(1, 1, '|') <----> (1, 1, '-') : 重み 1

ただし、スタートとゴール地点での方向転換は重み 0 にします。(スタート地点での方向転換は自由なので。)

今向いている方向への移動を表すリンクを重み 0 とします。

・(1, 1, '|') <----> (1, 2, '|') : 重み 0
・(1, 1, '-') <----> (2, 1, '-') : 重み 0

あとは、これらで構成される無向グラフについて、スタートからゴールの最小距離を検索します。(スタートとゴールでの方向は任意の方向を1つ決めればOK。スタートとゴール地点の方向転換は重み 0 に注意してください。)

一般には、ダイクストラを使えばOKですが、Python だとギリギリ TLE になります。

そこで、ダイクストラより効率的な 01-BFS を利用します。(これは、リンクの重みが 0 / 1 だけの場合に使えます。)

※ 01-BFS の解説はこちらがお勧め。
betrue12.hateblo.jp

で、実際の結果はこうなります。

atcoder.jp

いちおうパスしていますが、1838 ms で、けっこうギリギリ感はあります。

重み 0 でつながるノードを同一視

上記のコードでは、conv() 関数で、「座標 + 方向(0 / 1 で表現)」で表した状態を単一の数値のノード番号に変換しています。

仮に、(1, 1, 0) と (2, 1, 0) が重み 0 のリンクで繋がっていた場合、これらを区別せずに同一のノード番号にマッピングしてしまっても構いません。

ただし・・・・

それぞれのノードがリンクを持っている場合、それぞれのリンクを融合するという、ちょっと面倒な処理が必要になります。

なのですが・・・

上記のコードでは、リンク情報を構築する際に、

  for y in range(1, H+1):
    for x in range(1, W+1):

という方向にマス目をスキャンしながら、

・(x, y) から見て、右と下にあるマス目 (x+1, y)、および、(x, y+1) とのリンクを追加する

という処理をしています。(この順番であれば、左と上のマス目は、ダブルカウントになるので、考えなくてよいですよね・・)

そうすると・・・

・(x, y) から見て、右と下にあるマス目 (x+1, y)、および、(x, y+1) は、スキャン前なので、まだリンク情報を持っていません。

したがって、「(x+1, y)、もしくは、(x, y+1) を (x, y) と同一視する」という処理、つまり、「(x+1, y)、もしくは、(x, y+1) を (x, y) と同一のノード番号にマッピングする」という処理は、リンクの引き継ぎを気にせずに行うことができます。

ノードの同一視については、(Union-Find の発想を借りて)次のように実装します。

まず、conv() では、ノード番号を取得した後、さらにその親のノード番号を返すようにします。

def conv(x, y, d):
  global H, W, parent
  i = x + (y-1) * W + d * (H*W)
  if parent[i] == None:
    parent[i] = i
  return parent[i]

で、ノードを同一視させたくなったところで、親の情報を書き換えます。

      if exists(x+1, y):
        p0 = conv(x, y, 0)
        p1 = conv(x+1, y, 0)
        parent[p1] = p0

一般には、親の親を再帰的に検索する必要がありますが、今回の場合は、スキャンの順序を(落ち着いて)考えると、再帰的な検索は不要とわかります。

実際にこれを実装したのがこちらになります。

atcoder.jp

801 ms で、確かに高速化されました。(ちなみに、この処理をしておけば、ダイクストラでもギリギリ間に合いました。)

とことんやってみる

上記のコードでは、隣り合うマス目を(連鎖的に)同一視していますが、よく考えると、スタート地点とゴール地点の方向転換についても、同一視ができます。(スタートとゴールでは方向転換のリンクは重み 0 なので。)

ただし、この部分では、先に触れたノードの引き継ぎが必要になります。さらに、同一視の連鎖が一方向にならない可能性があるので、(本物の Union-Find と同様に)親の検索を再帰的に実装する必要があります。

def conv(x, y, d):
  global H, W, parent
  i = x + (y-1) * W + d * (H*W)
  if parent[i] == None:
    parent[i] = i
  while i != parent[i]:
    i = parent[i]
  return i

ここまでやる必要があるかは疑問ですが、仮に、ここまでやると、重み 0 のリンクが完全になくなり、重み 1 のリンクのみになります。なので、01-BFS ではなく、普通の BFS での探索が可能になります。

というわけで、ものは試しでやってみました。

atcoder.jp

965 ms とちょっと遅くなりました。親の再帰的な検索の時間がオーバーヘッドになっているような気がします。(たぶん。)