【蟻本】Pythonの二次元リストの初期化でハマった話

本日もPythonで蟻本をやってみたシリーズの記事です。
↓蟻本とはこちらです

リンク

で、今日はPythonの二次元リスト（二次元配列）の初期化でハマったのでその話についてです。

事の発端は迷路の最短路を求める幅優先探索

蟻本の以下の問題のプログラムをPythonで記述していた時のことでした。

大きさが N x M の迷路が与えられます。迷路は通路と壁からできており、1ターンに隣接する上下左右4マスの通路へ移動することができます。スタートからゴールまで移動するのに必要な最小のターン数を求めなさい。ただし、スタートからゴールまで移動できると仮定します。

で、これに対して解答を以下のようにPythonで書いて実行してみました。

import queue

INF = 100000000
N = int(input())
M = int(input())
maze = [list(input()) for i in range(N)]

for i in range(N):
  for j in range(M):
    if maze[i][j] == "S":
      sx = i
      sy = j
    elif maze[i][j] == "G":
      gx = i
      gy = j

dx = [1, 0 , -1, 0]
dy = [0, 1, 0, -1]

def bfs():
  d = [[INF*M]*N]

  q = queue.Queue()
  q.put([sx, sy])
  d[0][1] = 0

  while not q.empty():
    p = q.get()
    if p[0] == gx & p[1] == gy:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if (0 <= nx) & (nx < N) & (0 <= ny) & (ny < M):
        if (maze[nx][ny] != "#") & (d[nx][ny] == INF):
          q.put([nx, ny])
          d[nx][ny] = d[p[0]][p[1]] + 1

  return d[gx][gy]

res = bfs()
print(res)

しかし、これを実行してみたところ、正しい出力を得ることができませんでした。
直接の原因は、if文の中の処理が実行されていないことでした。

if (0 <= nx) & (nx < N) & (0 <= ny) & (ny < M):
    if (maze[nx][ny] != "#") & (d[nx][ny] == INF):
        #処理が書かれてるけど、ここが実行されていない

この原因を辿ってみたところ、リストdが想定していたような初期化ができていなかったのが根本原因でした。
解決のためには、21行目を以下の書き方に直すべきでした。

    d = [[INF*M]*N] #これが元々の21行目。間違い。
    d = [[INF for i in range(M)] for j in range(N)] #こう書くべき（これをリスト内包表記と言う）

二次元配列はリスト内包表記を使って初期化すべき

どうも元の書き方だと、「INFをM個並べたリストを、単にN個格納した二次元リスト」を生成してしまうようです。
一見なんの問題ないように聞こえますが、以下のコードを実行するとわかります。

list1 = [[0]*3]*2
list2 = [[0 for i in range(3)] for j in range(2)] #リスト内包表記

print("list1 = {0}".format(list1))
print("list2 = {0}".format(list2))
 
list1[0][1] = 1
list2[0][1] = 1
print("======")
print("list1 = {0}".format(list1))
print("list2 = {0}".format(list2))

上記のコードの実行結果がこちらです。

list1 = [[0, 0, 0], [0, 0, 0]]
list2 = [[0, 0, 0], [0, 0, 0]]
======
list1 = [[0, 1, 0], [0, 1, 0]]
list2 = [[0, 1, 0], [0, 0, 0]]

こんな感じです。面白いですね。
つまり、前者の場合は3つの要素を持つ同一のリストを単に並べた二次元リストで、後者の場合は3*2の要素を持つ二次元リストということになるようです。
（表現が合っているかは分からない。）

前者のようなリストを処理したいシーンはプログラミングコンテストでは稀だと思います。
なので、基本的に二次元リストはリスト内包表記を使って初期化する方が良さそうです。

それではまた〜。