Python AtCoder入門 第８講 2次元リストとグリッド問題

Python AtCoder入門 第8講 2次元リストとグリッド問題 AtCoderのB問題には、マス目 を扱う問題がよく出ます。 迷路、盤面、地図、表。 形は違っても、正体はすべて「縦H行・横W列に並んだマス」です。 1

今回のテーマ こうした問題を扱うための道具が、 2次元リスト です。 リストの中にリストが入っているもの、と考えてください。 2

この講のポイント 新しい概念は少なめです。 使うのは主に、 第4講の二重ループ 第5講のリスト 第6講の内包表記 です。 3

重要な罠 ただし、1つだけ知らないと必ずハマる罠があります。 [[0] * W] * H です。 これは一見便利ですが、2次元リストでは使ってはいけません。 4

コードファイル名の方針 この講でも、コード例ごとにファイル名を付けます。 grid_basic.py bad_grid.py char_grid.py numeric_grid.py neighbors.py answer_8_1.py 5

8-1 2次元リストの基本 2次元リストは、 リストを要素に持つリスト です。 grid = [[1, 2, 3], [4, 5, 6]] これは2行3列のマス目を表します。 6

grid[i][j] 要素には、 grid[i][j] でアクセスします。 print(grid[0][0]) print(grid[1][2]) 出力： 1 6 7

iが行、jが列 grid[i][j] の、 が行 j が列 です。 「上からi番目の行を取り出して、その中のj番目」と読みます。 どちらも0始まりです。 i 8

行数と列数 H = len(grid) W = len(grid[0]) が行数 len(grid[0]) が列数 です。 grid は「行のリスト」だからです。 len(grid) 9

内包表記による初期化 すべて0で埋めたH行W列のマス目は、次のように作ります。 grid = [[0] * W for _ in range(H)] 「長さWの行を、H個作る」という意味です。 10

grid_basic.py H = 3 W = 4 # Create an H x W grid filled with zeros grid = [[0] * W for _ in range(H)] # Set some cells grid[0][0] = 1 grid[1][2] = 5 grid[2][3] = 9 # Print row by row for row in grid: print(*row) # Size of the grid print(len(grid), len(grid[0])) 11

grid_basic.py の出力 1 0 0 0 0 0 5 0 0 0 0 9 3 4 出力は、 for row in grid: print(*row) で1行ずつ行います。 12

print(grid) は答え向きではない print(grid) とすると、角括弧だらけになります。 AtCoderの答えとしては、多くの場合WAです。 1行ずつ取り出して、 print(*row) で出力しましょう。 13

[[0] * W] * H がダメな理由 次の2つは一見同じに見えます。 grid = [[0] * W for _ in range(H)] grid = [[0] * W] * H # 正しい # 壊れる 下の書き方は、絶対に使ってはいけません。 14

何が壊れるのか [[0] * W] * H は、行をH個複製しているように見えます。 しかし実際には、 同じ1つの行への参照をH個並べているだけ です。 15

1マス変えると全行が変わる 同じ行を何度も指しているため、 bad[0][0] = 1 とすると、すべての行の先頭が 1 になります。 第5講の「コピーの罠」と同じです。 16

bad_grid.py H = 3 W = 4 # The wrong way bad = [[0] * W] * H bad[0][0] = 1 for row in bad: print(*row) print(bad[0] is bad[1]) print("---") # The right way good = [[0] * W for _ in range(H)] good[0][0] = 1 for row in good: print(*row) print(good[0] is good[1]) 17

bad_grid.py の出力 1 0 0 0 1 0 0 0 1 0 0 0 True --1 0 0 0 0 0 0 0 0 0 0 0 False bad では3行すべてが変わっています。 18

is の意味 bad[0] is bad[1] は、 まったく同じものか を調べています。 True なら、0行目と1行目が同じリストを指しているという意味です。 19

鉄則 2次元リストは必ず内包表記で作ります。 grid = [[0] * W for _ in range(H)] 1次元なら [0] * W で問題ありません。 罠になるのは「リストを * で繰り返したとき」です。 20

8-2 グリッド入力の受け取り AtCoderでよく出るのが、 # と . などが並んだマス目です。 3 4 #..# .##. #..# 1行目にHとW、続くH行にマス目が与えられます。 21

文字グリッドの受け取り 文字グリッドは、次の形で受け取れます。 H, W = map(int, input().split()) S = [input() for _ in range(H)] これで S は文字列のリストになります。 22

文字列のままアクセスできる 文字列はインデックスでアクセスできます。 print(S[0][0]) print(S[1][1]) でi行目の文字列。 その [j] でj文字目です。 2次元リストと同じ感覚で使えます。 S[i] 23

書き換えたい場合 文字列はイミュータブルなので、書き換えられません。 マス目を書き換えたい場合は、1文字ずつのリストにします。 S = [list(input()) for _ in range(H)] S[0][0] = "." 読むだけなら文字列のままで十分です。 24

char_grid.py # Read the grid size H, W = map(int, input().split()) # Read the grid as a list of strings S = [input() for _ in range(H)] # Count the '#' cells count = 0 for i in range(H): for j in range(W): if S[i][j] == "#": count += 1 print(count) 25

char_grid.py の実行例 入力例： 3 4 #..# .##. #..# 出力例： 6 全マスを二重ループで見ています。 26

全マス走査が基本 グリッド問題の基本は、 for i in range(H): for j in range(W): # マス (i, j) について処理 です。 第4講の二重ループそのものです。 27

数値グリッド 数値が空白区切りで並ぶ形式もあります。 2 3 1 2 3 4 5 6 この場合は、各行を整数リストとして受け取ります。 28

数値グリッドの受け取り A = [list(map(int, input().split())) for _ in range(H)] 第1講の入力テンプレートを、H行ぶん繰り返しています。 内包表記で短く書けます。 29

numeric_grid.py # Read the grid size H, W = map(int, input().split()) # Read the numeric grid A = [list(map(int, input().split())) for _ in range(H)] # Sum of each row for i in range(H): print(sum(A[i])) # Sum of each column for j in range(W): total = 0 for i in range(H): total += A[i][j] print(total) 30

numeric_grid.py の実行例 入力例： 2 3 1 2 3 4 5 6 出力例： 6 15 5 7 9 31

行の合計 行の合計は簡単です。 sum(A[i]) A[i] がi行目のリストそのものだからです。 32

列の合計 列の合計は、一発では取れません。 A[0][j] A[1][j] A[2][j] のように、縦にたどる必要があります。 「何を固定し、何を動かすか」を意識しましょう。 33

8-3 グリッド上の探索 グリッド問題の基本は、 二重ループで全マスを見る ことです。 for i in range(H): for j in range(W): # マス (i, j) について処理 34

count_cells.py # Read the grid size and the threshold H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] K = int(input()) # Count the cells whose value is K or more count = 0 for i in range(H): for j in range(W): if A[i][j] >= K: count += 1 print(count) 35

count_cells.py の実行例 入力例： 2 3 1 5 3 8 2 9 5 出力例： 3 5 , 8 , 9 の3つです。 36

隣接マス グリッド問題では、 あるマスの上下左右を調べる 処理がよく出ます。 マス (i, j) の隣は、 上： (i - 1, j) 下： (i + 1, j) 左： (i, j - 1) 右： (i, j + 1) 37

方向ベクトル 上下左右の移動量をリストにまとめます。 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] これを 方向ベクトル と呼びます。 中身はタプルのリストです。 38

方向ベクトルを使う for di, dj in directions: ni = i + di nj = j + dj は行の変化量 dj は列の変化量 ni , nj は隣のマス です。 di 39

範囲外チェック 隣を見るときは、必ず範囲外チェックをします。 if 0 <= ni < H and 0 <= nj < W: # ここで初めてアクセスしてよい 範囲外のマスにアクセスすると、エラーやWAの原因になります。 40

負のインデックスに注意 Pythonでは、 S[-1] がエラーになりません。 最後の行を指してしまいます。 範囲外チェックを忘れると、エラーが出ずに間違った答えになることがあります。 41

neighbors.py
# Read the grid
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# Four directions: up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# For each cell, count the adjacent '#' cells
for i in range(H):
row = []
for j in range(W):
count = 0
for di, dj in directions:
ni = i + di
nj = j + dj
if 0 <= ni < H and 0 <= nj < W:
if S[ni][nj] == "#":
count += 1
row.append(count)
print(*row)

42

neighbors.py の実行例 入力例： 3 3 .#. ### .#. 出力例： 2 1 2 1 4 1 2 1 2 43

全マス × 4方向 このコードは三重ループに見えます。 しかし、いちばん内側は必ず4回です。 つまり計算量は、 H × W × 4 です。 グリッド問題で何度も使う骨格です。 44

章末まとめ 2次元リストは、 リストのリスト です。 grid[i][j] の、 が行 j が列 です。 どちらも0始まりです。 i 45

章末まとめ：初期化 2次元リストの初期化は、 grid = [[0] * W for _ in range(H)] です。 これは使ってはいけません。 grid = [[0] * W] * H 46

章末まとめ：入力 文字グリッド： S = [input() for _ in range(H)] 書き換えるなら： S = [list(input()) for _ in range(H)] 数値グリッド： A = [list(map(int, input().split())) for _ in range(H)] 47

章末まとめ：走査 グリッド問題の基本は、二重ループです。 for i in range(H): for j in range(W): # マス (i, j) 全マスを1つずつ見ます。 48

章末まとめ：隣接マス 上下左右は方向ベクトルで扱います。 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] 範囲外チェックを必ず書きます。 if 0 <= ni < H and 0 <= nj < W: 49

練習問題 8-1 黒いマスの数 H行W列のマス目があります。 各マスは、 # ：黒 . ：白 です。 黒いマスの個数を出力してください。 50

練習問題 8-1：入力と出力 入力： H W S_1 S_2 ... S_H 入力例： 3 4 #..# .##. #..# 出力例： 6 51

answer_8_1.py # Read the grid H, W = map(int, input().split()) S = [input() for _ in range(H)] # Count the '#' cells count = 0 for i in range(H): for j in range(W): if S[i][j] == "#": count += 1 print(count) 全マス走査とカウントパターンです。 52

answer_8_1_count.py # Read the grid H, W = map(int, input().split()) S = [input() for _ in range(H)] # Count '#' in each row and sum them up print(sum(row.count("#") for row in S)) 文字列の count() を使うと短く書けます。 53

練習問題 8-2 行と列の最大合計 H行W列の数値が並んだ表があります。 各行の合計の最大値と、各列の合計の最大値を、この順に空白区切りで出力してください。 54

練習問題 8-2：入力と出力 入力例： 2 3 1 2 3 4 5 6 出力例： 15 9 行の最大合計は 15 。 列の最大合計は 9 です。 55

answer_8_2.py # Read the numeric grid H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] # Sum of each row row_sums = [] for i in range(H): row_sums.append(sum(A[i])) # Sum of each column col_sums = [] for j in range(W): total = 0 for i in range(H): total += A[i][j] col_sums.append(total) print(max(row_sums), max(col_sums)) 56

行の合計は内包表記でも書ける row_sums = [sum(A[i]) for i in range(H)] 行は A[i] でそのまま取り出せます。 列は縦にたどる必要があります。 57

練習問題 8-3 孤立した黒マス H行W列のマス目があります。 黒いマスのうち、 上下左右のいずれにも黒いマスが隣接していない ものを「孤立している」と呼びます。 孤立している黒いマスの個数を出力してください。 58

練習問題 8-3：入力と出力 入力例： 3 4 #..# .##. #..# 出力例： 4 四隅の4つの # が孤立しています。 59

answer_8_3.py
# Read the grid
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# Four directions: up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Count isolated '#' cells
answer = 0
for i in range(H):
for j in range(W):
if S[i][j] != "#":
continue
neighbors = 0
for di, dj in directions:
ni = i + di
nj = j + dj
if 0 <= ni < H and 0 <= nj < W:
if S[ni][nj] == "#":
neighbors += 1
if neighbors == 0:
answer += 1
print(answer)

60

answer_8_3.py のポイント 白いマスは判定する必要がありません。 if S[i][j] != "#": continue で次のマスへ進みます。 隣接する黒マスの数が 0 なら、孤立しています。 61

第8講まとめ この講では、 2次元リストとグリッド問題 を学びました。 B問題では、マス目を二重ループで走査する問題がよく出ます。 62

次回予告 次の第9講では、 関数と組み込み関数 を扱います。 ここまで書いてきた処理に名前を付けて整理する方法と、Pythonが用意している便利な関数を学びます。 63