幅優先探索（BFS）、深さ優先探索（DFS）の問題

幅優先探索と深さ優先探索は似たような問題をカバーできるけど、幅優先の方があんまり考えなくても実装できる（気がする）。幅優先はキュー、深さ優先はスタックと仲良し。

幅優先探索は、基本的に「次に訪れる島」をキューの形で保持しておくことが肝要です。import collections、collections.deque()、popleft()のおまじないを使っていきましょう。

A - Darker and Darker
（手数計算）
横wマス、縦hマスのグリッドがあり、白と黒で塗られている。1ターンごとに現在ある黒マスの上下左右を黒で塗る操作をすると、何ターンで全てのマスが黒マスになりますか、という問題。
最初の黒マスをターン0で塗れるものとし、1ターンごとに見ていき、次のターンで塗ったマスを手数+1足してキューに追加、それをキューが空になるまで続ける。全てのマスの中で最も手数が大きいものを出力。（Python3だとTLEする可能性がある）

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1130&lang=jp
（連結判定）
グリッド上に連結な点がいくつ存在するかを求める問題。

C - 幅優先探索
（最短経路）
迷路を幅優先で解く。一番上の問題とほぼ同じ要領でできる。

D: Grid Repainting - AtCoder Beginner Contest 088 | AtCoder
（最短経路）
実質迷路を解くのと同じ。最短経路のマス、#マス、.マスをそれぞれカウント。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
（最短経路）
有向グラフの最短距離は幅優先探索を使うといい。ワーシャルフロイドみたいなのは無向グラフとかで使おうね。

深さ優先探索

深さ優先探索は、次に訪れる島の情報をスタックの形式で保持しておくイメージです。行けるところまで行ったら戻ってくる、みたいな「わかりそうだけどわからない」説明よりかはデータ構造の違いでコードを書いていきたい。

深さ優先探索を使う問題

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

スタックを使う実例を下に載せる。

h,w = map(int,input().split())
C = []
stack = []
visited = []
for i in range(h):
    T = [0]*w
    visited.append(T)
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        L.append(s[j])
        if s[j] == 's':
            stack.append([i,j])
            visited[i][j] = 1
    C.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
flag = False
while len(stack) > 0:
    now = stack.pop()
    if C[now[0]][now[1]] == 'g':
        print('Yes')
        flag = True
    for i in range(4):
        y = now[0]+dy_dx[i][0]
        x = now[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if C[y][x] != '#' and visited[y][x] == 0:
                visited[y][x] = 1
                stack.append([y,x])
if not flag:
    print('No')

C - One-stroke Path

for文を使った再帰のような形。むずかし。

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
cnt = [0]
def dfs(V, s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1                    
    else:
        for adj in G[s]:
            if V[adj] == 0:             
                dfs(V[:adj] + [1] + V[adj + 1:], adj)  #ここで分岐がたくさん発生する
dfs([0] * N, 0)
print(cnt[0])

D - Fennec VS. Snuke

今見た島の隣の島を見る素直な実装で解ける。

n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
visited = [0]*n
visited[0] = 1
visited[n-1] = 1
visited_all = [1]*n
nextF = edge[0]
nextS = edge[n-1]
black = 1
white = 1
while visited != visited_all:
    l = []
    for f in nextF:
        if visited[f] == 0:
            visited[f] = 1
            black += 1
            for x in edge[f]:
                l.append(x)
            nextF = l
    l = []
    for s in nextS:
        if visited[s] == 0:
            visited[s] = 1
            white += 1
            for y in edge[s]:
                l.append(y)
            nextS = l
if black > white:
    print('Fennec')
else:
    print('Snuke')

塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

幅優先探索（BFS）、深さ優先探索（DFS）の問題