アルゴリズム力UP!『ARC 005 C 器物損壊！高橋君』を解いてみよう

記事を読むとわかること

• 記事の作者の『ARC 005 C 器物損壊！高橋君 』の解法がわかる
• 記事の作者のアルゴリズム問題へのアプローチがわかる

今回の問題

ARC 005 C 器物損壊！高橋君　→ 問題文はこちら

記事の作者の回答のコード

from collections import deque

# ==============================================================
# return: スタートとゴールなどを入力すると、高橋くんがたどり着けるかどうかを出力
# pre, post: 問題文に記載 -> 2 3 のマスの解釈を 3行目の2列目にあるマス というのではなく、2次元配列の2行目の3行目にあるマス　と最初考えた方が混乱しないかも。

# ==============================================================
# ★ step1 問題文を解くために必要な迷路をインプットする
# ★ step2 深さ優先探索でスタートからゴールにむかい上下左右に探索をさせる。(今回は塀を2回まで叩ける関係で幅優先だとTLEになる)
# ★ step3 塀を破壊した回数を記憶させ、壁を破壊するたびにインクリメントさせる
# ★ step4 探索で進む先のマスで0~2回で壁を破壊し進んだかを記憶させ、3以上の時に弾くようにさせる
# ★ step5 もしゴールにたどり着いた/着かなかった場合にYES/NOを返す

#問題文に則り迷路大きさをインプット
h, w = map(int, input().split())
#問題文に則り迷路をインプット
maze = [list(input()) for i in range(h)]

def dfs():

    #上下左右の4方向に分岐させる (今回は1行目の0行目みたいな解釈になるので、どの方向かは厳格に考えない方が無難？)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #あるマスを探索したかを壊した回数ごとに持つために、マスごとで[False, False, False]を持つ
    d = [[[False] * 3 for j in range(w)] for i in range(h)]


    #スタートとゴールのインデックスを探索し、それぞれ代入する
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "s":
                sx = i
                sy = j
            if maze[i][j] == "g":
                gx = i
                gy = j

    #スタックの作成(今回は深さ優先のため)
    que = deque([])
    #スタートをスタックにいれる(3つ目は塀を壊した回数)
    que.append((sx, sy, 0))
    #スタートマスに探索した記憶をつける
    d[sx][sy][0] = True

    while que:
        #popメソッドを使い後に入れたデータを先出し、深さ優先を表現 (イメージ、究極直線を進みまくる)
        p = que.pop()
        #ゴールか否かを判定
        if p[0] == gx and p[1] == gy:
            break
        #4方向を指定
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            #新しいマスに向かうに当たり、前回時点での破壊した回数を代入
            t = p[2]
            #迷路範囲外かどうかを判定
            if not (0 <= nx < h and 0 <= ny < w):
                continue
            # 次が壁でかつすでに2回壊してる状態がどうか
            if  maze[nx][ny] == "#" and t == 2:
                continue
            #既に探索済みかどうか
            if d[nx][ny][t]:
                continue
            # 塀なら壊して進む(上のifで既に回数のハンドリングは済んでいる)
            if maze[nx][ny] == "#":
                #塀の破壊回数をインクリメントしつつ新しいマスに記録
                que.append((nx, ny, t + 1))
                d[nx][ny][t + 1] = True
            else:
                #塀の破壊回数をそのままにしつつ新しいマスに記録
                que.append((nx, ny, t))
                d[nx][ny][t] = True

    #ゴールの座標を壊した回数でループし、いずれかにTrueがあればTrueを返す
    for i in range(3):
        if d[gx][gy][i]:
            return True

#ゴールにたどり着いたかどうか
if dfs():
    print("YES")
else:
    print("NO")

回答の解説

記事の作者が思う今回のアルゴリズム問題の回答ポイント

• 迷路やスタート及びゴールを入力する際、迷路が配列で扱う関係で０番目スタートであることを意識
• 深さ優先探索であるため、後入先出しのためのpopメソッドを使う
• 条件分岐として、迷路の範囲内か、塀でありかつ破壊回数が2回か、未探索先か壁か、を判断する
• 探索先に分岐に合わせてスタックに破壊回数を記録し進める

このコードの課題感

• 今回の前提として〜行目の〜行目のマスとしたが、仮に「2行２列目」がスタートであると解釈する場合、今回の変数x(列),y(行)がちょっと気持ちが悪くなる