[백준/Python3] 13023 ABCDE

https://www.acmicpc.net/problem/13023

풀이

일부 사람들이 친구일 때, A - B - C - D - E와 같은 친구관계가 존재하는지 구하는 문제다. DFS를 이용해 해결할 수 있다.

코드

import sys
input = sys.stdin.readline

# DFS
def dfs(target, num):
    if num == 4:
        print(1)
        exit()

    for node in graph[target]:
        if not visited[node]:
            visited[node] = True
            dfs(node, num + 1)
            visited[node] = False


# Initial
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    # Undirected Graph
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


visited = [False for _ in range(N)]

for node in range(N):
    visited[node] = True
    dfs(node, 0)
    visited[node] = False

print(0)