FUNCoder-第9回活動

第9回活動 2024/07/03 18:15~19:45 @593教室

トップページはこちら: FUNCoder

#2024-07-03 #グラフ理論 #DFS

/icons/hr.icon

はじめに

新規参加者も増えてきており、実力に差が見られるよになってきました。

本日は下記の内容を扱っていきますが、初学者には難しい内容となっています。

そのような方は FUNCoder-第4回活動の内容を追ってみてください。

バチャは以下のリンクになります（全員参加してください）

https://kenkoooo.com/atcoder/#/contest/show/cce8e47b-fd91-49f5-8d74-013435563ad5

※ 第4回活動に取り組む方はバチャの$ 3問目以降に取り組んでいってください。

下記の内容に取り組む方は座学後にバチャの$ 1,2問目、および AOJ の問題を解いていただきます（詳細に関しては後述しています）。

/icons/hr.icon

本日はグラフ理論について学習していきます。

「$ 1から資料を作るのは大変すぎる」 & 「既にわかりやすすぎる資料が存在する」のでそれをみながら解説をしていきます。

/icons/hr.icon

まずは DFS (Depth First Search) 入門の記事を読みつつ、グラフへの理解をしていきましょう。

DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【前編】

以下は C++ で書かれているコードを Python で表したものです。

code:グラフの入力受け取り.py

# 頂点数と辺数

N, M = map(int, input().split())

# グラフ

G = [[] for _ in range(N)]

for i in range(M):

a, b = map(int, input().split())

Ga.append(b)

# 無向グラフの場合は以下を追加

# Gb.append(a)

code:重み付きグラフの入力受け取り.py

# 頂点数と辺数

N, M = map(int, input().split())

# グラフ

G = [[] for _ in range(N)]

for i in range(M):

from_, to, weight = map(int, input().split())

Gfrom_.append((to, weight))

※ Python で from は予約語なので、重複を防ぐために from_ としています。

code:DFSテンプレ.py

import sys

sys.setrecursionlimit(500_000) # おまじない

def dfs(now: int):

# 今見ている頂点を訪問済みにする

seennow = True

# 頂点 now から行ける頂点 nxt を全探索する

for nxt in gnow:

# 頂点 nxt が既に訪問済みであれば探索を行わない

if seennxt:

continue

# if seennxt == True: continue # 上に同じ

# まだ探索を行っていない頂点であれば、新たに dfs を行う

dfs(nxt)

N, M = map(int, input().split())

g = [[] for _ in range(N)]

for i in range(M):

a, b = map(int, input().split())

# ここでは無向グラフを想定

ga.append(b)

gb.append(a)

# 重み付き無向グラフの場合

# a, b, c = map(int, input().split())

# ga.append((b, c))

# gb.append((a, c))

seen = False*N # seeni := 頂点 i を訪れたかどうか (i は 0-indexed)

# 頂点 0 から dfs を行う

dfs(0)

このコードが今日のメインです

/icons/hr.icon

ここからは以下の記事で続きを解説します。

後半戦です。

DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【後編】

練習問題 1

A - 深さ優先探索

ヒント & 注意事項

上下左右の$ 4方向を上手く処理する方法について考えてみましょう

テンプレートの for nxt in g[now] の部分がどうなるのか考えてみましょう

ここが最も重要な部分となります

解答例 (Python)

code:Python

import sys

sys.setrecursionlimit(500_000)

def dfs(now_y: int, now_x: int):

seennow_ynow_x = True

for dy, dx in d:

next_y = now_y + dy

next_x = now_x + dx

# 配列外参照を起こす場合は探索を行わない

if not (0 <= next_y < H and 0 <= next_x < W):

continue

# 壁の場合は探索を行わない

if Snext_ynext_x == "#":

continue

# 既に訪問済みの場合は探索を行わない

if seennext_ynext_x:

continue

dfs(next_y, next_x)

H, W = map(int, input().split())

S = input() for _ in range(H)

# 上下左右 4 方向の変化量

d = ((1, 0), (-1, 0), (0, 1), (0, -1))

# s と g を探す

for i in range(H):

for j in range(W):

if Sij == "s":

sy, sx = i, j

if Sij == "g":

gy, gx = i, j

# seenij := (i, j) を訪問したかどうか

seen = [False*W for _ in range(H)]

# 始点から dfs をする

dfs(sy, sx)

# 答えを出力する

if seengygx:

print("Yes")

else:

print("No")

/icons/hr.icon

練習問題 2

How Many Islands?

ヒント & 注意事項

上下左右の$ 4方向だけでなく、斜めの$ 8方向あることに注意してください

練習問題 1 と同様に、再帰を書くのであれば sys.setrecursionlimit() を付けてください

解答例 (Python)

code:Python

import sys

sys.setrecursionlimit(500_000) # おまじない

def dfs(now_y: int, now_x: int):

seennow_ynow_x = True

for dy, dx in d:

next_y = now_y + dy

next_w = now_x + dx

# 配列外参照なら探索を行わない

if not (0 <= next_y < H and 0 <= next_w < W):

continue

# 海であれば探索を行わない

if Snext_ynext_w == 0:

continue

# 既に探索済みの島であれば探索を行わない

if seennext_ynext_w:

continue

seennext_ynext_w = True

dfs(next_y, next_w)

while True:

# 入力を受け取る

W, H = map(int, input().split())

if (W, H) == (0, 0):

break

S = list(map(int, input().split())) for _ in range(H)

# 上下左右 + 斜めの 8 方向に対する変化量

d = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1))

seen = [False*W for _ in range(H)]

ans = 0 # 陸の数

for i in range(H):

for j in range(W):

# 陸でなければ探索を行わない

if Sij == 0:

continue

# 既に探索済みの陸であれば探索を行わない

if seenij:

continue

dfs(i, j)

ans += 1 # 陸の数 += 1

# 答えを出力する

print(ans)

/icons/hr.icon

練習問題 3

🧪 B - 埋め立て

ヒント & 注意事項

制約が$ H, W = 10とかなり小さいので全探索でも何でもできそうな感じはします。

全探索することを考えましょう。つまり、埋め立てられるマス全てに対して埋め立てた場合、Yes になるか？という問題に帰着できます

全探索した場合、埋めたマスはその探索が終わり次第、元に戻す必要があることに注意してください。これがこの問題の本質です

昔の ABC なので YES, NO であることに注意してください

解答例 (Python)

code:Python

import sys

sys.setrecursionlimit(500_000) # おまじない

def dfs(now_y: int, now_x: int):

seennow_ynow_x = True

for dy, dx in d:

next_y = now_y + dy

next_w = now_x + dx

# 配列外参照なら探索を行わない

if not (0 <= next_y < 10 and 0 <= next_w < 10):

continue

# 海であれば探索を行わない

if Anext_ynext_w == "x":

continue

# 既に探索済みの島であれば探索を行わない

if seennext_ynext_w:

continue

seennext_ynext_w = True

dfs(next_y, next_w)

A = list(input()) for _ in range(10)

# あらかじめ、前処理として島の数を数えておく

cnt = 0 # 島の数

for i in range(10):

for j in range(10):

if Aij == "o":

cnt += 1

# 上下左右に対する変化量

d = ((1, 0), (-1, 0), (0, 1), (0, -1))

for i in range(10):

for j in range(10):

# 既に島であれば探索を行わない

if Aij == "o":

continue

# 埋め立てる

Aij = "o"

seen = [False*10 for _ in range(10)]

# dfs で探索を行う

dfs(i, j)

num = 0 # 訪問済みの数、つまり True の個数を数える

for y in range(10):

for x in range(10):

if seenyx:

num += 1

# 埋め立てた分の +1 であるかどうかを判定する

if cnt + 1 == num:

print("YES")

exit()

# 埋め立てたマスを元に戻す

Aij = "x"

print("NO")

/icons/hr.icon