【Python】多次元配列の初期化の注意点！！！

初めに

競技プログラミングサイトAtcoderの以下の問題を解いていました。
普段はC++で解いていますが、pythonで解いているときに問題が起きました。

問題文

$3\times3$ のサイズのビンゴカードがあります。上から $i$ 行目、左から $j$ 列目の数は $A_{i, j}$ です。

続けて、 $N$ 個の数 $b_1, b_2, \cdots, b_N$ が選ばれます。選ばれた数がビンゴカードの中にあった場合、ビンゴカードのその数に印を付けます。

$N$ 個の数字が選ばれた時点でビンゴが達成されているか、則ち、縦・横・斜めのいずれか $1$ 列に並んだ $3$ つの数の組であって、全てに印の付いているものが存在するかどうかを判定してください。

問題リンク

宴会で盛り上がるビンゴの問題です。
ビンゴカードを$3\times3$のサイズのbool型2次元配列で管理すると解けそうです。

そして問題が起こった

初期化でやりたいこと

以下のようにビンゴカードをすべてのマスがFalseになるように準備します。

card = [[False, False, False],
        [False, False, False],
        [False, False, False]] 

この初期化であれば問題が起きることはありません。

問題が起きる初期化の仕方

しかし、サボって以下のような初期化をすると問題が起きます。

# よろしくない例1
card = [[False, False, False]] * 3

# よろしくない例2
card = [[False] * 3] * 3

私は実際に「よろしくない例2」で初期化をしました。

起きた問題

値を代入して書き換えてみます。
実際には$b_1, b_2, \cdots, b_N$に含まれている数のマスをTrueにするという操作ですが、説明のためにcard[0][0]を書き換えてみます。

# 初期化
card = [[False] * 3] * 3

# 値の書き換え (例:card[0][0]をTrueにする)
card[0][0] = True

# 確認
print(card)
# [[True, False, False], [True, False, False], [True, False, False]]

なんとcard[0][0]のみをTrueに書き換えたつもりだったのですが、card[1][0]とcard[2][0]も書き換えられてしまっています。

これは由々しき事態です。

原因

よろしくない例のように初期化すると要素であるリスト(行に対応するリスト)が全て同じオブジェクトとして生成されてしまう

# よろしくない例1
card = [[False, False, False]] * 3

# よろしくない例2
card = [[False] * 3] * 3

実際にアドレスを見てみると

card = [[False] * 3] * 3

for i in range(3):
    print(id(card[i]))

# 0: 2520503833544
# 1: 2520503833544
# 2: 2520503833544

確かに同じオブジェクトを指しているようです。
そりゃ、同時に値が書き換わるわけですね。。。

解決策

リスト内包表記で初期化すると違うオブジェクトとして生成されるようです。

# リスト内包表記による初期化
card = [[False] * 3 for _ in range(3)]

for i in range(3):
    print(f"{i}: {id(card[i])}")

# 0: 2459664737928
# 1: 2459664740296
# 2: 2459662013832

確かに違うオブジェクトとして生成されています。

まとめ

多次元配列(list)を初期化する場合は記述が増えても内包表記を使う。
まぁそもそもnumpyでよい！という話もあったりしそうではある。

<おまけ>無事にACしたコード

無事に問題の謎が解けました。
汚いですが一応載せておきます。

# input
A = [list(map(int, input().split())) for i in range(3)]
N = int(input())
b = [int(input()) for i in range(N)]

# bingo card
bi = [[False]*3 for i in range(3)]

# check
for i in range(3):
    for j in range(3):
        if A[i][j] in b:
            bi[i][j] = True

# flag of bingo
flg = False

# check row/col
for i in range(3):
    if(bi[i][0] and bi[i][1] and bi[i][2]): flg = True
    if(bi[0][i] and bi[1][i] and bi[2][i]): flg = True
  
# check diagonal
if(bi[0][0] and bi[1][1] and bi[2][2]): flg = True
if(bi[0][2] and bi[1][1] and bi[2][0]): flg = True

# print answer
if flg: print("Yes")
else: print("No")