Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

【AtCoder】深さ優先探索(DFS)の典型的な問題を解く

More than 1 year has passed since last update.

競プロ強くなりたいので、このサイト(AtCoder 版!蟻本 (初級編))を参考に、AtCoderの問題を解いてアルゴリズムの基礎固めしています。今回解くのは、AtCoderのA-深さ優先探索。全探索の一種である深さ優先探索(DFS)の典型的な問題です。

問題

東西南北の長方形の街にて、途中の塀を通らず、道を通って、家から魚屋へたどり着けるかという問題です。
※ちなみにこの問題を幅優先探索(BFS)で解くと、辺の重みなしの最短経路問題になります。

解法

今回は再帰を使わず、スタックしていく方法で解きます。Wikipediaの深さ優先探索のページがアルゴリズムの概要がわかりやすいです。

解くポイントとしては、

■DFS一般的な部分

  • スタックを作成し、未訪問のノードを入れていく
  • 訪問したノードには、訪問済みの印をつける
     ※閉路がある場合に必要
  • スタックから一つずつ取り出し、処理を行う
     ※スタックなので「後入れ、先出し」。これがDFSを実現している。

■この問題特有の部分

  • スタートの位置がわからないので、初めに調べる(=スタックに入れておく)
  • 親ノード(x, y)に接続しているノードは、(x-1, y), (x+1, y), (x, y-1), (x, y+1)の4通り

といったところでしょうか。
以下、pythonのコードです。

from collections import deque

H,W = map(int, input().split())
C = [input() for _ in range(H)]

# sの位置をあらかじめ調べておく
for n1,c_w in enumerate(C):
    for n2,c in enumerate(c_w):
        if c == "s":
            s_h = n1
            s_w = n2

stack = deque([[s_h, s_w]])  # スタートの位置だけ入ったスタックを作成

visited_list = [[0]*W for _ in range(H)]
visited_list[s_h][s_w] = 1

def dfs(town, visited_list, stack):
    while len(stack) > 0:
        h, w = stack.pop()
        if town[h][w] == "g":
            return "Yes"
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if town[new_h][new_w] != "#" and visited_list[new_h][new_w] == 0:
                visited_list[new_h][new_w] = 1
                stack.append([new_h, new_w])

    return "No"

print(dfs(C, visited_list, stack))
gh_takumi
競プロ強くなりたい
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away