※ 記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。
問題文
※ 東京大学側から指摘があった場合は問題文を削除いたします。
第１問
第２問
解答＆解説
テーマ: グラフ
迷路ということで、これは明らかにグラフをテーマにしている問題となります。
第一問
（１）
maze1.txtは掲示されていないので以下の様な迷路と想定します。
このれ迷路を表すmaze1.txtは以下の様なファイルとなります。
1,4,3,2,4,3,5,4 まずはテキストファイルから壁の情報を取得するretrieve_walls関数を以下のように作成します。
def retrieve_walls(file_path: str):
with open(file_path, mode='r') as f:
line = f.readlines()[0]
row_col_arr = line.rstrip().split(',')
wall_num = len(row_col_arr)//2
walls = []
for i in range(wall_num):
col, row = int(row_col_arr[i*2]), int(row_col_arr[i*2+1])
walls.append((col, row))
return walls取得された壁データの中身は以下の様になります。
file_path = "maze1.txt"
print(retrieve_walls(file_path))# 壁データの中身
[(1, 4), (3, 2), (4, 3), (5, 4)]問題文では迷路を解答用紙に書けということなのでこれを元に書けば良いです。
以下はデバッグ用に迷路をプリントアウトする関数ですが、実際のテストでは全部の問題を解き終わって余力がある時にでも実装すると良いでしょう。
# debug用でこの関数は別に必要はない
# n: 迷路の一辺の長さ
def show_maze(n, wall_set):
# 迷路の上辺
print(" " + "- " * n)
for i in range(n):
line = "|"
for j in range(n-1):
line += (" ")
if (2*i+1, 2*j+2) in wall_set:
line += "|"
else:
line += " "
line += " |"
print(line)
if i < n-1:
line2 = " "
for j in range(n):
if (2*i+2, 2*j+1) in wall_set:
line2 += "- "
else:
line2 += " "
print(line2)
# 迷路の下辺
print(" " + "- " * n)file_path = "maze1.txt"
walls = retrieve_walls(file_path)
wall_set = set(walls)
show_maze(3, wall_set) - - -
| | |
| | |
-
| | |
- - - （２）
3辺が壁のセルと名言してあるので、各セルについて上下左右の4方向の内、壁がちょうど3つあるものをカウントすれば良いです。その際に壁に関してはセットで保持しておくと参照しやすいので以下の解答コードではその様にしています。
# 時間計算量: O(n*n)
def count_deadspace(n, wall_set):
ret = 0
for i in range(n):
for j in range(n):
wall_cnt = 0
# up
if i == 0 or (2*i, 2*j+1) in wall_set:
wall_cnt += 1
# down
if i == n-1 or (2*i+2, 2*j+1) in wall_set:
wall_cnt += 1
# left
if j == 0 or (2*i+1, 2*j) in wall_set:
wall_cnt += 1
# right
if j == n-1 or (2*i+1, 2*j+2) in wall_set:
wall_cnt += 1
if wall_cnt == 3:
ret += 1
return ret maze2.txtは作るのが少々大変なので私が作ったmaze1.txtを代用して挙動の確認をします。
file_path = "maze1.txt"
walls = retrieve_walls(file_path)
wall_set = set(walls)
count_deadspace(3, wall_set)3実際に私が作成したmaze1は以下の様に袋小路はちょうど3つです。
（３）
最短経路なので、グラフを作成して幅優先探索（BFS）を使用すれば解くことができます。まずは以下の様に隣接リストのグラフを作成しましょう。
# 壁のタプルを毎回書くのが面倒だったので、以降では以下の様な関数を使用します
def up_wall(i, j):
return (2*i, 2*j+1)
def down_wall(i, j):
return (2*i+2, 2*j+1)
def left_wall(i, j):
return (2*i+1, 2*j)
def right_wall(i, j):
return (2*i+1, 2*j+2)
def create_graph(n, wall_set):
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
graph = [[] for _ in range(n*n)]
for i in range(n):
for j in range(n):
u = i*n+j
for k in range(4):
vi, vj = i+dy[k], j+dx[k]
if 0 <= vi and vi < n and 0 <= vj and vj < n:
v = vi*n + vj
# up
if k == 0 and not (up_wall(i, j) in wall_set):
graph[u].append(v)
# right
if k == 1 and not (right_wall(i, j) in wall_set):
graph[u].append(v)
# down
if k == 2 and not (down_wall(i, j) in wall_set):
graph[u].append(v)
# left
if k == 3 and not (left_wall(i, j) in wall_set):
graph[u].append(v)
return graphこの問題でもmaze3.txtは作るのが少々大変なので私が作ったmaze1.txtを代用してまずはグラフが正しく作れているかを確認します。
file_path = "maze1.txt"
walls = retrieve_walls(file_path)
wall_set = set(walls)
graph = create_graph(3, wall_set)
print(graph)[[1, 3], [4, 0], [5], [0, 6], [1, 5], [2, 8, 4], [3, 7], [6], [5]]以下は書くセルに対応するノードの番号を表示した迷路の図となりますが、上記のグラフが合っていることが確認できます。
後はこのグラフに対してBFSを実行して最短経路を求めましょう。
from collections import deque
# 時間計算量: O(N), N = len(graph)
def bfs(graph, start, end):
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
N = len(graph)
visited = [False for _ in range(N)]
que = deque([(start, 1)])
while que:
u, ud = que.popleft()
if visited[u]:
continue
visited[u] = True
if u == end:
return ud
for v in graph[u]:
if visited[v]:
continue
que.append((v, ud+1))
# 問題文より必ず辿り着けるとあるが、ない場合-1を返すことでデバッグができる
return -1maze1に対してスタートが0（左上）, ゴールが8（右下）のセルとした実行結果で挙動の確認をします。
ans = bfs(graph, 0, 8)
print(ans)5最短経路は以下の図の様に正しく5と求められていることがわかります。
（４）
この問題は慣れていない方にとってはちょっと難しめかもしれません。特に「任意の2マスの経路が必ずちょうど1つ存在する」をどう解釈すれば良いかわからないと思います。
先に答えから言うと、この問題では要はグラフが木であるかを尋ねているだけです。
- 任意の2マスにおいて必ず経路が存在 → グラフが連結
- 任意の2マスの経路は1つ → 閉路がない
と言う様に解釈できます。
後は木であるかを確認するコードを書きましょう。
# 時間計算量: O(N), N = len(graph)
def is_tree(graph):
N = len(graph)
visited = [False for _ in range(N)]
global visited_cnt
visited_cnt = 0
# 閉路があるかを検出するdfs, 閉路があればTrueを返す
# p: parent
def dfs(u, p):
visited[u] = True
global visited_cnt
visited_cnt += 1
for v in graph[u]:
if v == p:
continue
if visited[v]:
return True
# 子v以下に閉路が存在
if dfs(v, u):
return True
return False
has_cycle = dfs(0, -1)
# 木である条件は閉路なしかつ全てのノードに到達可能
return (not has_cycle) and (visited_cnt == N) この問題でもmaze10.txt ~ maze19.txtは作るのが少々大変なので私が作ったmaze1.txt代用して動作を確認します。実際のテストではmaze10.txt ~ maze19.txtそれぞれのグラフに対してis_tree関数を実行してTrueとなるものを答案に書けば良いです。
print(is_tree(graph))True第二問
（１）
sequence.txtを読み取って配列にするだけです。
def retrieve_sequence(file_path: str):
with open(file_path, mode='r') as f:
line = f.readlines()[0]
return [int(i) for i in line.rstrip().split(',')]（２）
(2-a)
第一問ですでに壁をどの様なデータ構造で扱うかを示してくれているのでその通りにやれば良いです。今まで同様に壁のデータをsetで管理すれば自動で重複を排除してくれます。
def get_wallset_from_sequence(n, sequence):
wall_set = set([])
for i in range(1, n):
for j in range(1, n):
s = i*n + j
ps = sequence[s]
if ps == 0:
wall_set.add(up_wall(i, j))
elif ps == 1:
wall_set.add(left_wall(i, j))
elif ps == 2:
wall_set.add(down_wall(i-1, j-1))
elif ps == 3:
wall_set.add(right_wall(i-1, j-1))
return wall_setこの問題でもp.txtは作るのが少々大変なので、私が作ったmaze1の壁データとなる以下のテキストmaze1_p.txtを使用して挙動の確認をします。
0,0,0,0,1,3,0,0,1 実際にmaze1_p.txtからmaze1のwall_setが作れているかをshow_maze関数で確認してみましょう。
file_path = "maze1_p.txt"
maze1_p_sequence = retrieve_sequence(file_path)
wall_set = get_wallset_from_sequence(3, maze1_p_sequence)
show_maze(3, wall_set) - - -
| | |
| | |
-
| | |
- - - この様にきちんとmaze1のwall_setが作れていることがわかります。
後は以下の様な関数を準備しておいて問題文の各セルについて調べれば良いです。
# 上下左右それぞれについて壁がある場合はTrueを返す
def get_wall_situation(n, i, j, wall_set):
u, d, l, r = False, False, False, False
if i == 0 or up_wall(i, j) in wall_set:
u = True
if i == n-1 or down_wall(i, j) in wall_set:
d = True
if j == 0 or left_wall(i, j) in wall_set:
l = True
if j == n-1 or right_wall(i, j) in wall_set:
r = True
return u, d, l, r
(2-b)
L字型なので以下の様な上と右に壁がなく、左と下に壁があるセルの数を数えれば良いです。
def count_L_number(n, wall_set):
ret = 0
for i in range(n):
for j in range(n):
u, d, l, r = get_wall_situation(n, i, j, wall_set)
if (not u) and d and l and (not r):
ret += 1
return ret
# より厳密にL字型を数える
def strict_count_L_number(n, wall_set):
ret = 0
for i in range(1, n):
for j in range(n-1):
u, d, l, r = get_wall_situation(n, i, j, wall_set)
u1, d1, l1, r1 = get_wall_situation(n, i-1, j+1, wall_set)
if ((not u) and d and l and (not r) and
(d1 or l1)):
ret += 1
return ret 確認としてmaze1対して実行した結果は以下の様になります。
count_L_number(3, wall_set)2
この様に確かに2つのL字型があることがわかります。
ただしこの問題では迷路であることを前提としているので、この様なパターンは存在しないと仮定しています。（
count_L_numberではこのパターンを想定していません。） 
strict_count_L_number の様にセル(i, j)に対して、さらに追加条件として、セル(i-1, j+1)の左または下の少なくともどちらか一方に壁があるという条件を追加すれば良いです。そうすると以下の様に必ずL字型となります。 
（３）
(3-a)
問題文の操作の通り迷路を作成していきます。この問題でも今まで同様にwall_setを求めていきます。初めは全てのセルは壁に囲まれているので、wall_setには最初全ての壁を含ませます。その後問題文の操作の通りに壁を取り除いていきます。
コード自体は以下の様に長くなってしまいますが丁寧に解いていきましょう。この問題は結構実装力も問われるのでそれなりに難しいかと思われます。neighbor.txtとcell.txtが手元にないので以下のコードの挙動の確認はできていませんが考え方自体はこの通りです。
def is_closed_cell(n, i, j, wall_set):
u, d, l, r = get_wall_situation(n, i, j, wall_set)
return u and d and l and r
# neighborとcellから迷路のwall_setを作成して返す
def create_maze(n, neighbor, cell):
# up, right, down, left
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
wall_set = set([])
for i in range(n):
for j in range(n):
if i > 0:
wall_set.add(up_wall(i, j))
if i < n-1:
wall_set.add(down_wall(i, j))
if j > 0:
wall_set.add(left_wall(i, j))
if j < n-1:
wall_set.add(right_wall(i, j))
len_n = len(neighbor)
len_c = len(cell)
cur_i, cur_j = 0, 0
cur_s = 0
# 時間計算量: O(n*n)
# neighborで次のセルを見つけた場合毎回1つ壁が外れる。壁は高々O(n*n)個しかない
while True:
find_next_by_neighbor = False
for s in range(cur_i+cur_j, len_n):
ns = neighbor[s]
next_i, next_j = -1, -1
if ns == 0: # up
next_i, next_j = cur_i-1, cur_j
elif ns == 1: # left
next_i, next_j = cur_i, cur_j-1
elif ns == 2: # down
next_i, next_j = cur_i+1, cur_j
elif ns == 3: # right
next_i, next_j = cur_i, cur_j+1
if 0 <= next_i and next_i < n and 0 <= next_j and next_j < n and is_closed_cell(n, next_i, next_j, wall_set):
find_next_by_neighbor = True
if ns == 0: # up
wall_set.remove(up_wall(cur_i, cur_j))
elif ns == 1: # left
wall_set.remove(left_wall(cur_i, cur_j))
elif ns == 2: # down
wall_set.remove(down_wall(cur_i, cur_j))
elif ns == 3: # right
wall_set.remove(right_wall(cur_i, cur_j))
cur_i, cur_j = next_i, next_j
break
if not find_next_by_neighbor:
find_next_by_cell = False
for t in range(2*(cur_i // cur_j), len_c, 2):
ct, ct1 = cell[t], cell[t+1]
cell_closed = is_closed_cell(n, ct, ct1, wall_set)
if cell_closed:
continue
has_closed_neighbor_cell = False
for d in range(4):
next_ct, next_ct1 = ct + dy[d], ct1 + dx[d]
has_closed_neighbor_cell |= is_closed_cell(n, next_ct, next_ct1, wall_set)
if has_closed_neighbor_cell:
break
if has_closed_neighbor_cell:
find_next_by_cell = True
cur_i, cur_j = ct, ct1
break
if not find_next_by_cell:
break
return wall_set create_mazeによってwall_setが作れたので後は問題文が指定したセルに対してget_wall_situationを実行して各方向の壁の有無を確認すれば良いです。
(3-b)
wall_setが求まっているのでcount_L_numberかstrict_count_L_numberを実行するだけで良いです。
(3-c)
縦横のそれぞれの方向での最長とその数を求めれば良いです。
from collections import defaultdict
def get_longest_straight_path(n, wall_set):
# key: dist, value: 長さdistのまっすぐな経路の個数
dist2count = defaultdict(int)
# i行目の横方向のまっすぐな経路の長さを数える
for i in range(n):
j = 0
l = 1
while j < n:
if j == n-1:
dist2count[l] += 1
else:
if right_wall(i, j) in wall_set:
dist2count[l] += 1
# reset
l = 1
else:
l += 1
j += 1
# j列目の縦方向のまっすぐな経路の長さを数える
for j in range(n):
i = 0
l = 1
while i < n:
if i == n-1:
dist2count[l] += 1
else:
if down_wall(i, j) in wall_set:
dist2count[l] += 1
# reset
l = 1
else:
l += 1
i += 1
max_l = max(dist2count.keys())
return max_l, dist2count[max_l] 私が作成したmaze1に対して実行すると、最長のまっすぐな経路の長さは3で、それが2つあることがわかります。
file_path = "maze1.txt"
walls = retrieve_walls(file_path)
wall_set = set(walls)
get_longest_straight_path(3, wall_set)(3, 2)
(3-d)
最終問題は難しいです。図などを書いて丁寧に考える必要があります。ただ一歩一歩しっかりと考えれば決して解けない問題ではないです。
まずこの問題では進行方向を管理する必要があります。これはある程度慣れている方にとってはすぐ思いつくテクニックかと思います。そしてここからが重要で、左に壁がある様に沿って歩くので、初期状態は「進行方向の左に壁がある」という状態にすることでwhile文で各ステップの操作が書ける様になります。
以下の様に右側進行で進行方向の左側（セルとして上側）に壁がある初期状態を考えてみましょう。すると以下の図の様に壁の有無によって幾つかの場合分けが起こることがわかります。全ての場合において最終的に進行方向の左側に壁がある初期状態に戻るまで操作を進めましょう。
コードは長いですが、それぞれの方向同士は対称的になっているので、1つの方向についてしっかりと考察すれば後は同じようにするだけです。
def go_aside_left_wall(n, wall_set, ei=39, ej=27):
# up, right, down, left
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
# 現在向いている方向
# cur_d: 現在向いている方向
# 0: up, 1: right, 2: down, 3: left
cur_d = 1
# 現在位置
cur_i, cur_j = 0, 0
# 進んだ長さ
l = 1
while not (cur_i == ei and cur_j == ej):
if cur_d == 0: # up
if up_wall(cur_i, cur_j) in wall_set:
cur_d = 1
else:
cur_i -= 1
l += 1
if cur_i == ei and cur_j == ej:
break
if left_wall(cur_i, cur_j) in wall_set:
continue
cur_j -= 1
l += 1
if cur_i == ei and cur_j == ej:
break
if down_wall(cur_i, cur_j) in wall_set:
cur_d = 3
continue
cur_i += 1
l += 1
if cur_i == ei and cur_j == ej:
break
cur_d = 2
elif cur_d == 1: # right
if right_wall(cur_i, cur_j) in wall_set:
cur_d = 2
else:
cur_j += 1
l += 1
if cur_i == ei and cur_j == ej:
break
if up_wall(cur_i, cur_j) in wall_set:
continue
cur_i -= 1
l += 1
if cur_i == ei and cur_j == ej:
break
if left_wall(cur_i, cur_j) in wall_set:
cur_d = 0
continue
cur_j -= 1
l += 1
if cur_i == ei and cur_j == ej:
break
cur_d = 3
elif cur_d == 2: # down
if down_wall(cur_i, cur_j) in wall_set:
cur_d = 3
else:
cur_i += 1
l += 1
if cur_i == ei and cur_j == ej:
break
if right_wall(cur_i, cur_j) in wall_set:
continue
cur_j += 1
l += 1
if cur_i == ei and cur_j == ej:
break
if up_wall(cur_i, cur_j) in wall_set:
cur_d = 1
continue
cur_i -= 1
l += 1
if cur_i == ei and cur_j == ej:
break
cur_d = 0
elif cur_d == 3: # left
if left_wall(cur_i, cur_j) in wall_set:
cur_d = 0
else:
cur_j -= 1
l += 1
if cur_i == ei and cur_j == ej:
break
if down_wall(cur_i, cur_j) in wall_set:
continue
cur_i += 1
l += 1
if cur_i == ei and cur_j == ej:
break
if right_wall(cur_i, cur_j) in wall_set:
cur_d = 2
continue
cur_j += 1
l += 1
if cur_i == ei and cur_j == ej:
break
cur_d = 1
return l総評
第一問ではグラフの知識、第二問では実装力を問うバランスの良い問題セットになっているかと思います。実際の試験では7割取れれば良いので第一問はできれば完答しましょう。第二問の実装は最初のwall_setを作る部分で失敗すると軒並み不正解になるので、ここは頑張りましょう。第二問の(3-d)は正直余裕がある人向けかと思います。丁寧な考察が必要なので時間的に厳しいかと思いますし、ここはできなくなても大丈夫かと思います。