【やってみた】AtCoder 版！蟻本 (初級編)の 2-1-2と2-1-3に類題にチャレンジ

初めに

• 筆者はAtCoderを取り組み始めたアラフォー・Unコーダである(非ソフトウェア職)

• AtCoder 版！蟻本 (初級編)に蟻本記載例題の類似問題が記載されている

• 上記記事著者である、けんちょん (Otsuki)@drken氏に感謝

目的

• AtCoder 版！蟻本 (初級編)に記載の探索系の問題の類題の回答と解説を掲載する

• 筆者が上記問題を解くことで、上記探索系のアルゴリズムの理解を深める

• 筆者は過去に同問に挑み道半ばで倒れてしまったため、リベンジする

• 諸兄（姉）からの指摘を受けることで見落としていた課題を補完する

まとめ

• 類題を解き解説をつけることができた。
• 解説を書きながら要点を整理することで、典型的なDFSとBFSの問題であれば本番でも対処できる力がついたと感じた。
• 数をこなして周辺問題の理解を深めるアプローチで、以前は理解できなかった問題が解けるようになった。

2-1-2(DFS)

DFS典型コード

• numpy.whereとか使いたくなるが、激重なのでNG
• collection.queとlistのスライスで攻めるのが◎

import collections
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

stack = collections.deque()
fp = [[0 for _ in range(W)] for _ in range(H)]



stack.append(start) #任意の開始ポイント
is_found = False

fp[start[0]][start[1]] = 1
goto = [[1, 0], [0, 1], [-1, 0], [0, -1]]


while stack:
    temp = stack.pop()
    y, x = temp

    if grid[y][x] == 'g':
        is_found = True
        stack = False
        # 探索終了条件
    elif grid[y][x] == '#':
        pass
        #障害物
    else:
        for i in range(4):
            nx = x + goto[i][0]
            ny = y + goto[i][1]

            if 0 <= nx <= W-1 and 0 <= ny <= H-1:
                if fp[ny][nx] == 0:
                    stack.append([ny, nx])
                    fp[ny][nx] = fp[y][x] + 1

print('Yes') if is_found else print('No')

ATC 001 A 深さ優先探索

方針

• ド定番
• 再帰で書く方が簡単だが、while文の方が変数のやり取りが分かりやすと感じた
• 本番でアレンジすることを考えてwhile文の書き方を習得しておく方がよさそう

import collections
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

stack = collections.deque()
fp = [[0 for _ in range(W)] for _ in range(H)]

start = False
for i in range(H):
    for j in range(W):
        if grid[i][j] == 's':
            start = [i, j]
            break
    if start:
        break

stack.append(start)
is_found = False

fp[start[0]][start[1]] = 1
goto = [[1, 0], [0, 1], [-1, 0], [0, -1]]

while stack:
    temp = stack.pop()
    y, x = temp
    # print(x,y)
    # print(grid[y][x])

    if grid[y][x] == 'g':
        is_found = True
        stack = False
    elif grid[y][x] == '#':
        pass
    else:
        for i in range(4):
            nx = x + goto[i][0]
            ny = y + goto[i][1]

            if 0 <= nx <= W-1 and 0 <= ny <= H-1:
                if fp[ny][nx] == 0:
                    stack.append([ny, nx])
                    #.pop()中身が[y,x]だからここも揃える
                    fp[ny][nx] = fp[y][x] + 1
                    # print('next', nx, ny)

print('Yes') if is_found else print('No')

ARC 031 B 埋め立て

方針

• 全座標を対象にそこをoに変えたらどうなるか探索する
• 最初からoのところは1回だけ探索しておいてそれ以外は無視しても良いが、コードが複雑になりそうなため全部トライする。

実装

• copy.deepcopy()を用いて毎回新しい盤面を用意した
• 探索済みの座標を'#'に塗り替えることで、YESであれば最終番手後に一色となるように工夫した。

import copy
import collections
grid = [[item for item in input()] for _ in range(10)]

is_found = False

for i in range(10):
    for j in range(10):
        if grid[i][j] == 'o':
            start = [i, j]
            is_found = True
            break
    if is_found:
        break

def dfs(grid, start):
    stack = collections.deque([start])
    is_found = False

    goto = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    while stack:
        temp = stack.pop()
        y, x = temp
        grid[y][x] = 'x'

        for i in range(4):
            nx = x + goto[i][0]
            ny = y + goto[i][1]

            if 0 <= nx <= 9 and 0 <= ny <= 9:
                if grid[ny][nx] == 'o':
                    stack.append([ny, nx])
                    #.pop()中身が[y,x]だからここもy,x順に揃える
                    grid[ny][nx] = 'x'

    for i in range(10):
        for j in range(10):
            if grid[i][j] != 'x':
                return False
    return True

is_slove = False

for i in range(10):
    for j in range(10):
        temp_grid = copy.deepcopy(grid)
        temp_grid[i][j] = 'o'

        if dfs(temp_grid, start):
            is_slove = True
            break
    if is_slove:
        break

print('YES') if is_slove else print('NO')

ARC037B バウムテスト

以前理解できなかった問題だった。
筆者にとってはマイルストーン的な問題である。

方針

• 「木である　=　閉路がない」と読み替える
  • 閉路とは一度訪れたノードに再び訪れる経路があること
  • ただし、直前に訪れたノード（親ノード）へ帰る経路は無視する

実装

• 直前に訪れたノードがどれかお覚えておくことが大事。
• 以下コードでは、stackに次のノードを積む際に現在ノードを次ノードの親としてセットした。
  • stack.append([next_node, temp_node])

解答

import collections

N, M = [int(item) for item in input().split()]
path_list = [[int(item) for item in input().split()] for _ in range(M)]

edges = [[] for _ in range(N+1)]

for a, b in path_list:
    edges[a].append(b)
    edges[b].append(a)

stack = collections.deque()
fp = [0 for _ in range(N+1)]

def dfs(start):
    prev = -1
    stack.append([start, prev])

    is_roop = False
    while stack:
        temp_node, prev = stack.pop()
        next_edges = edges[temp_node]
        fp[temp_node] = 1

        if next_edges != []:
            for next_node in next_edges:
                if next_node != prev:
                    if fp[next_node] == 1:
                        is_roop = True
                    else:
                        stack.append([next_node, temp_node])

    return False if is_roop else True

cnt = 0
for i in range(1,N+1):
    if fp[i] == 0:
        if dfs(i):
            cnt += 1
print(cnt)

2-1-3(BFS)

BFSの典型コード

import collections
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

fp = [[-1 for _ in range(W)] for _ in range(H)]

# position[y, x]
# start [0,0]
# goal [H-1, W-1]

que = collections.deque([[0, 0, 1]])
fp[0][0] = 1
next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
is_found = False

while que:
    temp = que.popleft()

    if temp[0] == H-1 and temp[1] == W-1:
        pass_num = temp[2]
        que = False
        is_found = True
    else:
        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] == -1:
                    que.append([ny, nx, temp[2]+1])
                    fp[ny][nx] = temp[2] + 1

print(pass_num) if is_found else print(-1)

ABC007 幅優先探索

方針

• 典型的なBFS

実装

• 使いまわせるように工夫した
• 足跡を記録するfp配列
  • -1で初期化
  • 開始地点を0で初期化
  • que追加の際に足跡を記録
• 行先をd_y_x_listとして問題に応じて登録することで、上下左右以外の方向で動いても対応可
• 入れる値受ける値を配列のスライス順に合わせてy,xの順序で処理した
• 次の番手目が分かるようにqueに次の番手目を加えた
• 次の番手目が枠をはみ出しているか判定するために、ny, nxを計算しif文でフィルタした

import collections

R, C = [int(item) for item in input().split()]
sy, sx = [int(item) for item in input().split()]
gy, gx = [int(item) for item in input().split()]

grid = [[item for item in input()] for _ in range(R)]

fp = [[-1 for _ in range(C)] for _ in range(R)]

res = 0
que = collections.deque([[sy-1, sx-1, 0]])
fp[sy-1][sx-1] = 0

d_y_x_list = [[1, 0], [0, 1], [-1, 0,], [0, -1]]

while que:
    y, x, cnt = que.popleft()

    if y == gy-1 and x == gx-1:
        res = cnt
        que = False

    else:
        for dy, dx in d_y_x_list:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= R-1 and 0 <= nx <= C-1:
                if grid[ny][nx] != "#" and fp[ny][nx] == -1:
                    que.append([ny, nx, cnt + 1])
                    fp[ny][nx] = cnt + 1
                    # print(ny, nx, cnt + 1)

print(res)

JOI2010 E

方針

• 繰り返し計算するので、始点・終点探しと探索とを関数化する

実装

• 工夫はない

import collections
H, W , N = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

def find_pos(S):
    is_found = False
    for i in range(H):
        for j in range(W):
            if S == 0:
                if grid[i][j] == 'S':
                    sy = i
                    sx = j
                    is_found = True
                    return sy, sx
            else:
                if grid[i][j] == str(S):
                    sy = i
                    sx = j
                    is_found = True
                    return sy, sx


def path_num(start, goal):
    sy, sx = find_pos(start)
    gy, gx = find_pos(goal)
    que = collections.deque([[sy, sx, 0]])
    fp = [[-1 for _ in range(W)] for _ in range(H)]
    d_y_x_list = [[1, 0], [0, 1], [-1, 0,], [0, -1]]

    while que:
        y, x, cnt = que.popleft()

        if y == gy and x == gx:
            return cnt

        else:
            for dy, dx in d_y_x_list:
                ny = y + dy
                nx = x + dx

                if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                    if grid[ny][nx] != "X" and fp[ny][nx] == -1:
                        que.append([ny, nx, cnt + 1])
                        fp[ny][nx] = cnt + 1

res = 0
for num in range(N):
    res += path_num(num, num+1)

print(res)

ABC088D - Grid Repainting

方針

• 黒く塗っても最短経路でゴールできる場合が解になる
• ゴールした経路を求めて、それ以外を黒塗ればいい
  • 問われているのは個数だから正確なルート座標は分からなくてもいい
  • 最短経路の手数さえわかればよい
• もともと黒い所は色が変えられないのだから点数にならない
• よって解は「全マス数　-　最短経路の手数　-　もともと黒の個数」となる

実装

• 普通にBFSで最短経路の手数求めただけ
• 答えが見つからない場合もあるので、ゴールが見つかったときにis_found　= Trueにする。

import collections
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

fp = [[-1 for _ in range(W)] for _ in range(H)]

que = collections.deque([[0, 0, 1]])
fp[0][0] = 1
next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
is_found = False

while que:
    temp = que.popleft()

    if temp[0] == H-1 and temp[1] == W-1:
        pass_num = temp[2]
        que = False
        is_found = True
    else:
        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] == -1:
                    que.append([ny, nx, temp[2]+1])
                    fp[ny][nx] = temp[2] + 1

black_cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            black_cnt += 1

if is_found:
    print(H*W - black_cnt - pass_num)
else:
    print(-1)

AGC033A

方針

• 最初に#をqueに入れる
• 訪れた座標を記録するgridの最初の#に1を入れる
• 最初の#の回りから何手で広がることができるかBFSで調べる
• 一番遠い座標の手数が解

実装

• pythonだとTLEした
• pypy3でクリア

import collections
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

fp = [[-1 for _ in range(W)] for _ in range(H)]

que = collections.deque()
next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]


for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            que.append([i, j, 0])
            fp[i][j] = 0

while que:
    temp = que.popleft()

    for dy, dx in next_y_x:
        ny = temp[0] + dy
        nx = temp[1] + dx

        if 0 <= ny <= H-1 and 0 <= nx <= W-1:
            if fp[ny][nx] == -1:
                que.append([ny, nx, temp[2]+1])
                fp[ny][nx] = temp[2] + 1

temp_max_list = []
for line in fp:
    temp_max_list.append(max(line))

print(max(temp_max_list))

ARC005C - 器物損壊！高橋君

方針

• 壁がないところはコスト0で行く
• 壁があるところは通過にコスト1で行く
• ゴールにたどり着くまでに使えるコストは2までに制限する
• 同じ場所に異なるコストでたどり着く場合があるので、低コストたどり着く方を優先する
• BFSで一度通った所もコストが異なれば再度通っても良いとすると、永遠にqueが消えないので工夫が必要

• よって、同コストでたどり着ける範囲を調べて、そこからコスト+1で辿りつける座標を見つける事とする

  • コストが増加しない座標を全て調べる
  • 訪問済みの座標は評価しない
  • コストが増加しないが表を調べ終わってから壁を通過してコストを１増やす

• 上記工夫は01BFSという手法

  • BFSと銘打っているが、DFSとBFSを条件で分けて使っている
  • queとstackのデータ構造を巧く利用する考え方
  • 上記記事によると01BFSのBFSは幅優先探索でなく、「最良優先探索(Best-First Search)」という言葉が適していると指摘している。

実装

• 01BFSのデータの持ち方が味噌
  • dequeで次座標のデータを持つ
  • BFSの拡張と考えて、popleft()でデータを取り出す
  • コストが変わらない座標を優先探索するので、上記dequeにappendleft()する
• 上記のように走査することで全ての座標に最低コストでアクセスすることになるので、一度訪れた座標は評価しなくても良い

import collections
H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

fp = [[-1 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if grid[i][j] == 's':
            start = [i, j]
        if grid[i][j] == 'g':
            goal = [i, j]


que = collections.deque([[start[0], start[1], 0]])
fp[start[0]][start[1]] = 0
next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
is_found = False

while que:
    temp = que.popleft()

    if temp[0] == goal[0] and temp[1] == goal[1]:
        que = False
        is_found = True
    else:
        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and fp[ny][nx] == -1:
                if grid[ny][nx] == '#':
                    if temp[2] < 2:
                        que.append([ny, nx, temp[2]+1])
                        fp[ny][nx] = temp[2]+1
                else:
                    que.appendleft([ny, nx, temp[2]])
                    fp[ny][nx] = temp[2]


print('YES') if is_found else print('NO')