[백준] 13023: ABCDE (Python)

문제📖

풀이🙏

• DFS를 활용하여 모든 노드에서 확인을 하며 depth가 4 이상일 경우 1을 출력하고 종료한다.
• 한 노드뿐이 아니라 모든 노드에서 depth를 확인해야 하므로 dfs작업 이 후에 visited[i] = False로 초기화한다.

코드💻

import sys
# 최대 재귀 횟수 제한을 풀어줌
sys.setrecursionlimit(10000)

v, e = map(int, input().split())
graph = [[] for i in range(v)]
visited = [False] * v

for i in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(cnt, v):
    if cnt == 4:
        print(1)
        sys.exit(0)

    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(cnt+1, i)
            visited[i] = False

for i in range(v):
    visited[i] = True
    dfs(0, i)
    visited[i] = False

print(0)