[Algorithm] BaekJoon : 13023. ABCDE by Python

[問題のショートカット]https://www.acmicpc.net/problem/13023

📌問題の説明

BOJアルゴリズムキャンプにはN人が参加している.人々は0番からN-1番で、友达がいる.
今日は以下のような友人関係のある人A,B,C,D,Eが存在するかどうかを検討してみましょう.

AとBは友達です.

BとCは友達です.

CとDは友達です.

DとEは友達です.

上記の友人関係があるかどうかを判断するプログラムを作成してください.
入力
第1行は、人の数N(5≦N≦2000)と友人関係の数M(1≦M≦2000)を与える.
2行目から、M行には整数aとbがあり、aとbが友達であることを示す.(0≦a,b≦N−1,a≠b)2回以上の友人関係はない.
しゅつりょく
問題条件に合致するA,B,C,D,Eがあれば、1がなくて出力0となる.

💡 問題を解く

問題は簡単すぎて、出題者の意図が理解できません...
最初はA-B-C-D-E...N-1まで友達関係だと思って集合した.(もちろん…「失敗」)
しかし、質問で求められるのはA→B→C→D→Eの関係、すなわち5の友人関係の有無を深く理解することである.
5人の「深さ」を探す必要があるのでDFSアルゴリズムで解決した.
0からN-1までDFSにナビゲートし、深さ5の友人関係があれば1を出力!
すべてのナビゲーションが完了するまで関係が存在しない場合は、0を出力します.
コードは次のとおりです.

import sys

def dfs(node, depth, visited):
    global flag
    if depth == 5: # 깊이 5의 친구 관계가 존재하면 True
        flag = True
        return
    for idx in relationship[node]:
        if not visited[idx]:
            visited[idx] = True
            dfs(idx, depth+1, visited)
            visited[idx] = False

N, M = map(int, input().split())
relationship = {i:[] for i in range(N)}
for _ in range(M):
    s, e = map(int, sys.stdin.readline().split())
    relationship[s].append(e)
    relationship[e].append(s)

flag = False # 조건에 맞는 '친구 관계' 존재 유무
for node in range(N):
    if not flag:
        visited = [False] * N
        visited[node] = True
        dfs(node, 1, visited)
    else: # 조건에 맞는 친구 관계를 찾았으면 탐색을 멈춘다.
        break
print(1) if flag else print(0)

アルゴリズムはやはり問題を理解するのが最も重要で最も難しいです...😂