AtCoderのC問題を解く：一筆書きグラフ問題
ABC054のone stroke problemを解いてみました。
ようするに無向グラフで一筆書きできる経路の数を求めよ、というものです。
ちなみに参考にしたのは以下のブログでほぼ同じことが書かれてしまっています
再帰を使った無向グラフの経路全探索
問題設定：
以下、atcoderのスクショを貼ります。
こちらからも見れるかな？
C- one stroke path
この問題を解いていきましょう！
流れ
グラフの情報はinputから読み取ることとします。以下が流れです。
1.無向グラフを表す行列を作り、inputから読み込んだ情報をもとに初期化する
2.訪問したことのあるノードについての情報を入れるvisitedリストをつくる
3.グラフ上にいる位置、深さをループごとに更新し、一番深いところまで来たら、探索終了とする
3では再帰関数を使うのですが、これがちょっと最初は理解しにくいかもしれないです。
コードは以下です。
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())
path_matrix = []
#無向行列の初期化
for n in range(N):
path_matrix.append([False] * N)
#まず無向グラフを表す行列を作る
for m in range(M):
line = map(int, input().split())
paths = [x - 1 for x in line]
path_matrix[paths[0]][paths[1]] = True
path_matrix[paths[1]][paths[0]] = True
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N
#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
if visited[now]:
return 0
if depth == N - 1:
return 1
visited[now] = True
total_paths = 0
for i in range(0, N):
if path_matrix[now][i]:
total_paths += dfs(i, depth + 1)
visited[now] = False
return total_paths
print(dfs(0, 0))
再帰関数dfsのやろうとしていること
再帰関数dfsでやろうとしていることは要するにもし飛べる先があるのなら、その飛んだ先のノードで今いる位置と深さを更新した上で、もっと掘り下げてみる、ということです。
・これでもし更新された深さが一番深ければ、そこで経路は全探索されたものとしてtotal_pathsに1が足されます。
・もしもうすでに訪問したノードに再びたどりついてしまったら、total_pathsに0が足されます。（つまり、何も足されない）
最後に一応これ以降引き続き処理を行う場合のために現在位置のvisitedをFalseに戻しています。
検証
実際にデータを入力してみましょう
Input:
3 3
1 2
1 3
2 3
Output:
2
Input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7
Output:
2
最後に
2ヶ月前に競技プログラミングをはじめたのですが、まったくC問題が解けないので、ここでどんどんアウトプットしていこうと思います。再帰関数、深い！