Atcoder水色への精選 100 問　深さ優先探索(Python)

AtCoder Python 競プロ精進 精選100問 深さ優先探索

水色になるための精選100問、
今回は24~27までの「深さ優先探索」です

再帰は前から苦手だったので理解するいい機会になりました

qiita.com

前回↓
二分探索
algo-archit.hatenablog.com

目次



24　ALDS_11_B - 深さ優先探索

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B

深さ優先探索では、目的のノードをみつけるか、探索できる子ノードがなくなるまで探索を行っていきます
スタックを使った方法や再帰関数を用いた解き方ができます

この問題ではたどり着いた時間だけでなくそのノードについて一通り調べ終わった順番まで記録しなければいけなかったので再帰的な手法で解きました

ネットワークとして全てのノードがつながっているとは限らない点に注意です

pythonでの実装例

n = int(input())
v_list = [[] for _ in range(n+1)]

for _ in range(n):
    li = list(map(int,input().split()))
    u,k = li[:2]
    v = li[2:]
    v.sort()
    v_list[u] += v

inf = 10**8

d = [inf for _ in range(n+1)]
f = [inf for _ in range(n+1)]

time = 1

def dfs(now):
    global time

    # 探索済みだった場合中断
    if d[now] != inf:
        return

    d[now] = time
    time += 1

    for i in v_list[now]:
        dfs(i)
    
    f[now] = time
    time +=1

# 1番目から探索を開始（孤立ノードに注意）
for i in range(1,n+1):
    dfs(i)

    print(i,d[i],f[i])



25　AOJ 1160 - 島はいくつある？

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160

まずW＊H個のすべてのマスについて１つづつ探索を行います
未だ探索されておらず、かつ島のマスがあった場合、そのマスを始点として深さ優先探索を隣接する8マスに対して行います
また島の個数を１カウント増やします

この際、探索をし終わった島のマスを海のマスに変更することで重複して島をカウントするのを防ぐことができます

pythonでの実装例

while True:
    w,h = map(int,input().split())

    if w == 0 and h == 0:
        break

    c = [list(map(int,input().split())) for _ in range(h)]
    visited = [[0 for i in range(w)]for j in range(h)] # 訪問したか確認

    island = 0 # 島の個数
    xy_move = []
    
    # 8方向のパターン
    for i in range(-1,2):
        for j in range(-1,2):
            if not(i == 0 and j == 0):
                xy_move.append([i,j])

    # 全てのマスに関して探索　
    for i in range(w):
        for j in range(h):
            # 海or探索済みだった場合打ち切り
            if visited[j][i] == 1 or c[j][i] == 0:
                continue

            stack = [[i,j]]
            island += 1

            while stack:
                x,y = stack.pop()
                c[y][x] = 0 # 自身は塗りつぶす

                for k in xy_move:
                    x_move,y_move = k
                    nx = x+x_move
                    ny = y+y_move

                    if 0 <= nx < w and 0 <= ny < h and c[ny][nx] == 1 and visited[ny][nx] == 0:
                        visited[ny][nx] = 1
                        c[ny][nx] = 0 # 自身は塗りつぶす
                        stack.append([nx,ny])

    print(island)



26　AtCoder Beginner Contest 138 D - Ki

問題文
atcoder.jp

「各 i (1 ≤ i ≤ N −1)に対して頂点 ai が bi の親であるとは限らない」（解説引用）ため、再帰を使わない深さ優先探索では問題を解くことができません（コンテスト本番中はこの制限に引っかかるテストケースがなかったためACできたみたいですがAfter Contestテストケースが追加されました）

そこで親ノードに至るまでの加算値を再帰関数の引数として残しておき、自身の加算値と合計したのちに子ノードに引き継ぐという方針を取りました

自分のノードが加算値の対象になるかを辞書型を用いて管理しています（リストでも問題なし）

pythonでの実装例

from collections import defaultdict
from sys import setrecursionlimit # 再帰エラー対策
setrecursionlimit(10 ** 7)

n,q = map(int,input().split())

connection = [[] for _ in range(n+1)]
counter = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
point_dic = defaultdict(int)

for _ in range(n-1):
    a,b = map(int,input().split())
    connection[a].append(b)
    connection[b].append(a)

# 各ノードの加算値を記録
for _ in range(q):
    p,x = map(int,input().split())
    point_dic[p] += x

# 現在のノード(node)とそれまでに加算された値(before_point)
def dfs(node,before_point):
    if visited[node]:
        return
    
    # 現在のノードの加算値を足す
    if point_dic[node]:
        point = point_dic[node]+before_point
    else:
        point = before_point
    
    # 訪問済みにする
    visited[node] = 1
    counter[node] += point

    for i in connection[node]:
        if visited[i]:
            continue

        dfs(i,point) # 再帰して子ノードに引き継ぐ

dfs(1,0)

print(' '.join(map(str, counter[1:])))



27　JOI 2009 予選 4 - 薄氷渡り

問題文
atcoder.jp

氷を適切に割っていった際に何区間移動できるかを聞いた問題です

移動を行う際に、現在の深さを引数にとっておき、移動後の深さがそれまでの最大深さより大きい値になった場合更新をします

またその地点を訪問した際の広場のリスト(どこまで氷を割ったかのリスト)を見るために、再帰したときに一旦氷を割る動作を行い
その地点から行きうるすべての地点を探索し終わったら氷を元の状態に戻します

M*N個のすべての地点からスタートした際の最大深さがどうなるかを調べればOKです

現在の状態をこのように保持するやり方は知らなかったので新鮮でした

pythonでの実装例

m = int(input())
n = int(input())

place = [list(map(int,input().split())) for _ in range(n)]
move = [[-1,0],[1,0],[0,-1],[0,1]]
max_depth = 0 # 最大で行ける深さ

def dfs(x,y,now_depth):
    global depth

    place[y][x] = 0 # 氷を割る

    if now_depth > depth:
        depth += 1 # 深さの最大値を超えた場合更新する

    for x_move,y_move in move:
        nx = x+x_move
        ny = y+y_move

        if 0 <= nx < m and 0 <= ny < n and place[ny][nx] == 1:
            dfs(nx,ny,now_depth+1)
    
    place[y][x] = 1 # 元に戻す(地点を探索する前のリストの状態にする)
        
# 全てのマス目に対して可能性を試す
for i in range(n):
    for j in range(m):
        if place[i][j] == 0:
            continue
        
        depth = 0
        dfs(j,i,1)

        max_depth = max(max_depth,depth)

print(max_depth)

↓次回　幅優先探索
algo-archit.hatenablog.com