(백준) 13023 ABCDE 파이썬

문제분석

첫 줄에 입력으로 노드의 수와 간선의 수가 주어진다.
다음 줄 부터는 친구들간의 관계가 주어진다.

문제의 목적의 DFS를 통하여 DFS의 Depth가 조건에 만족하는 경우 1을 출력하고 아니면 0을 출력하는 문제이다.

DFS를 실행하면서 depth를 같이 count해주고 depth가 문제의 조건과 일치한다면 1을 출력하고 아니면 0을 출력하면 된다.

코드 구현

# 파이썬 재귀 제한 풀어주기
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

# 노드와 간선의 갯수 입력받기
n, m = map(int, input().split())

visited = [False] * n # dfs 방문 초기화

graph = [ [] for _ in range(n)] # 빈 그래프 만들어주기
# 양방향 엣지
for _ in range(m): # 그래프 입력 받아주기
    a, b = map(int, input().split())
    graph[b].append(a)
    graph[a].append(b)

# dfs 구현, depth까지 지정
def dfs(start, depth):
    if depth == 4:
        print(1)
        exit()
    next = graph[start]
    for i in next:
        if not visited[i]:
            visited[i] = True
            dfs(i, depth + 1)
            visited[i] = False

# 노드 마다 dfs실행
for i in range(n):
    visited[i] = True
    dfs(i, 0)
    visited[i] = False

print(0)