LoginSignup
5
5

More than 1 year has passed since last update.

@tetsuro731(テッツォ)

【AtCoder 典型90問】003 - Longest Circular Roadを丁寧に解説【Python3】

Last updated at Posted at 2021-12-28

概要

  • 今回取り扱う問題 (AtCoder典型90問より)

問題の解き方に加えて、以下の理解を目的にする。

  • AtCoderをはじめとする競プロでよく使われる**深さ優先探索（DFS）と幅優先探索（DFS）**を理解する
  • 隣接行列と隣接リストの違い、使い分けについて理解する

問題設定

この問題ではDFSまたはBFSを使って適当な点から最も遠い距離を求める。
さらにその点から最も遠い点を求めることで木の直径を求めるという問題。
愚直にやろうとすると全ての二点の組み合わせの距離が必要なので$O(N^2)$となるが、
この方法だと$O(N)$で求まる。
inputとして以下を考えてみる。

入力
5
1 2
1 5
3 5
4 5

コード内では配列の添字を0スタートにしたいので、問題文の数字から1引いて考える。
頂点の数Nに対して辺の数がN-1なので、閉路を持たない木構造であることがわかる。
図にするとこんな感じ。

スクリーンショット 2021-12-28 13.04.40.png

初期位置の0から最も遠いのが3。3から最も遠いのが1となり、これが直径 = 3となる。
あとは直径の両端の1と3を結べば答えの4が出る。
ここでの0->3, 3->1をそれぞれdfsまたはbfsで求める。

深さ優先探索（DFS）で解く

まずはDFSを使った回答例。
DFSではスタックを使う。
スタックはFILO (First In Last Out) の特徴を持つ。
これを使うことで、「深く行けるところまで行く」というDFSを実装できる。

DFS
N = int(input())
# 無向グラフ, list連結
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

# 深さ優先探索
# ある点sから各点までの距離をdistに格納
def dfs(s):
    dist = [-1] * N  # 初期化
    dist[s] = 0  # 自分自身との距離は0
    st = [s]  # スタックを用意
    while st:
        v = st.pop()
        for nv in G[v]:
            if dist[nv] == -1:
                st.append(nv)
                dist[nv] = dist[v] + 1
    return dist


# 0から最も遠い点を求める
dist0 = dfs(0)
index = dist0.index(max(dist0))
# その点からさらに最も遠い点を求め、長さを直径とする
r_dist = dfs(index)
# 直径に1を加えたものが答えとなる
print(max(r_dist) + 1)
出力
4

図にするとこんな感じ。

スクリーンショット 2021-12-28 13.10.43.png

再起関数を使って解く

同じdfsでもstackではなく再帰関数を使って解くこともできる。
以下のようにhelper()を定義する。

再起関数
def helper(s, G, dist):
    for nv in G[s]:
        if dist[nv] == -1:
            dist[nv] = dist[s] + 1
            helper(nv, G, dist)
    return dist
  
 
# 深さ優先探索
# ある点sから各点までの距離をdistに格納
def dfs(s):
    dist = [-1] * N  # 初期化
    dist[s] = 0  # 自分自身との距離は0
    st = [s]  # スタックを用意
    return helper(s, G, dist)

なお、Pythonの場合は再起関数の呼び出し回数の上限がデフォルトで1000になってるので注意。
（このまま提出すると一部REになってしまう）
コードの先頭に以下の追加すれば大丈夫。

sys.setrecursionlimit(1000000)

幅優先探索（BFS）で解く

DFSではキューを使う。
キューはFIFO (First In First Out) の特徴を持つ。
これを使うことで、「同じ深さを探索してから次へ行く」というBFSを実装できる。
コードは基本的にはDFSと同じだが、dfs()を以下のbfs()に置き換える。
Pythonの場合はdequeを使えばいい。

BFS
from collections import deque

def bfs(s):
    dist = [-1] * N  # 初期化
    dist[s] = 0  # 自分自身との距離は0
    deq = deque([s]) # queを用意
    while deq:
        v = deq.popleft()
        for nv in G[v]:
            if dist[nv] == -1:
                deq.append(nv)
                dist[nv] = dist[v] + 1
    return dist

図にするとこんな感じ。

スクリーンショット 2021-12-28 13.35.07.png

DFS v.s. BFS

Q： どちらを使うべきか？
A： この問題に関してはどちらでも良い

「この問題に関しては」ということに注意。
例えば以下のような閉路を含むようなグラフで二点間の最短距離を求めるような問題だと、BFSを使ったほうが良い。

スクリーンショット 2021-12-28 13.46.50.png

0から4までの最短経路を求めたい場合、DFSだと0->2->3->4を先に探索して距離3であるが、実際の最短経路は
0->1->4で距離2である。
BFSの場合は0からの距離が1の点、2の点...と順番に探索していくため、より効率よく最短ルートを求めることができる。
一方で今回の問題は木構造であり2点を結ぶルートが1通りしかないため、どちらでも変わらない。

隣接リスト v.s 隣接行列

これまでのコード内では暗黙のうちに隣接リストを使っていたが、隣接行列を使う手法もある。

隣接リスト

頂点の数だけリストを作り、そこに連結している頂点を追加していく。
これまでと同様のinputだと以下のようになる。

G = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
print(G)

[[1, 4], [0], [4], [4], [0, 2, 3]]

0番目のリストには[1,4]が入ってることから、0には1,4が連結していることがわかる。
連結している部分だけを繋いでいるので無駄がなく、疎なグラフ（頂点に数に対して辺が少ない）場合にも対応できる。
初期化の時点でリストの要素数はN個あればいい。

隣接行列

一方で最初にN*Nの行列を用意して、(i,j)成分に頂点iとjの関係を対応させる方法もある。
これを隣接行列という。

# 隣接行列
AB = [[0]*N for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB[a][b] = 1
    AB[b][a] = 1
for i in AB:
	print(*i)

0 1 0 0 1
1 0 0 0 0
0 0 0 0 1
0 0 0 0 1
1 0 1 1 0

例えば行列の(0,1)(0,4)成分が1になっているので、ここが繋がっていることがわかる。
今回の設定では方向のないグラフ（無向グラフ）なので行列はi,j成分に対して対称になっている。
さて、この隣接行列を使って今回の問題を解いたらどうなるだろう？

N = int(input())
# 無向グラフ, 隣接行列
AB = [[0]*N for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB[a][b] = 1
    AB[b][a] = 1
    
# 深さ優先探索
# ある点sから各点までの距離をdistに格納
def dfs(s):
    dist = [-1] * N  # 初期化
    dist[s] = 0  # 自分自身との距離は0
    st = [s]  # スタックを用意
    while st:
        v = st.pop()
        for nv, val in enumerate(AB[v]):
            if val != 1:
              continue
            if dist[nv] == -1:
                st.append(nv)
                dist[nv] = dist[v] + 1
    return dist


dist0 = dfs(0)
index = dist0.index(max(dist0))
r_dist = dfs(index)
print(max(r_dist) + 1)

このコードはサンプルケースだと通るものの、提出するとREとTLEが出て死ぬ。
この問題だとN<100000のため、N~100000のとき、行列を使うと初期化のときに$N^2=10^{10}$個の要素のメモリを確保する必要があり、リソースが足りない。
このように、隣接行列を使う場合はメモリをどれくらい使うかを考える必要がある。

一般論として、

  • 隣接リストのメリット

    • メモリ消費が少ない
    • 疎なグラフでも無駄がない
    • 要素の追加、削除が容易

  • 隣接リストのデメリット

    • 要素へ参照する際に走査する必要がある

  • 隣接行列のメリット

    • 配列なので、要素へのアクセスが速い

  • 隣接行列のデメリット

    • メモリ消費が大きい
    • 要素の追加、削除にコストがかかる

が挙げられる。
ただし、Pythonのlistの場合は"list"という名前とは裏腹にその実態は配列なので、ここでいうリストの特徴には当てはまらないことがあるので注意。
これについては本筋からずれるので詳細には語らないが、Pythonのlistの仕様を見てみるとわかる。

まとめ

  • 今回の問題では、計算方法を工夫することで$O(N^2)$ではなく$O(N)$で計算できるようになる
  • 問題を通してDFS、BFSの違いを学んだ
  • 問題を通して隣接行列、隣接リストの違いを学んだ
  • 今回のケースだと...
    • DFS、BFSのどちらでも解くことができる
    • 隣接リストを使う必要がある
5
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
5