이번 문제는 DFS의 백트레킹을 활용하여 연결된 친구들을 모두 탐색하며, 그 연결의 길이가 5일 경우에 1을 출력하도록 하였다. 이렇게 접근하기 위해서 데이터를 인접 리스트로 저장하였고, dfs함수 내에서는 각각의 인접 리스트를 순회하며 방문처리되지 않은 친구에게 방문하도록 하였다.

Code

n, m = map(int, input().split())
relation = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    relation[a].append(b)
    relation[b].append(a)
def dfs(cur, path):
    if len(path) == 5:
        print(1)
        quit()
    for nxt in relation[cur]:
        if not visited[nxt]:
            visited[nxt] = True
            dfs(nxt, path+[nxt])
            visited[nxt] = False
for man in range(n):
    visited = [False for _ in range(n)]
    visited[man] = True
    dfs(man, [man])
print(0)