ATC001 A - 深さ優先探索

AtCoder Python3 DFS

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions
sys.setrecursionlimit(10000000)
ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def dfs(s, visit, C):
    h = s[0]
    w = s[1]
    if len(C) <= h or 0 > h or len(C[0]) <= w or 0 > w:
        return

    if visit[h][w] != 0:
        return

    if C[h][w] == '#':
        return

    visit[h][w] = 1
    dfs([h + 1, w], visit, C)
    dfs([h, w + 1], visit, C)
    dfs([h - 1, w], visit, C)
    dfs([h, w - 1], visit, C)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    C = [iss() for _ in range(H)]
    visit = [[0] * W for _ in range(H)]
    s = [0, 0]
    for h in range(len(C)):
        if 's' in C[h]:
            w = C[h].index('s')
            s = [h, w]
            break

    g = [0, 0]
    for h in range(len(C)):
        if 'g' in C[h]:
            w = C[h].index('g')
            g = [h, w]
            break
    dfs(s, visit, C)
    print('Yes' if visit[g[0]][g[1]] == 1 else 'No')


if __name__ == '__main__':
    main()

考え方

与えられた地図を元に、深さ優先探索を行う。
具体的には、スタートの位置から上下左右に移動し、

  • 移動範囲内であること（0 <= h < H, 0 <= w < W)
  • 訪問済みではないこと
  • 塀(#)ではないこと

3点を満たしていた場合には移動を行う。
その後、移動した点から上下左右に移動を行うことで、全ての移動できる範囲を探索する。

気を付ける点は再帰処理の最大上限を設定すること。
pythonのデフォルトでは再帰処理が1000回しか行うことができないため、
下記の記述で再帰の上限を変更しないとエラーとなる。

import sys
sys.setrecursionlimit(10000000)

ちなみに、この問題ではゴール(g)に到達した時点で処理を打ち切っていいので、
深さ優先探索(DFS)中、ゴールに到達したとき処理を終了させることで、少しだけ効率よくなる。
例：Submission #13382355 - AtCoder Typical Contest 001