문제

풀이

문제에서 N의 범위가 최대 2000이기에 visited를 2001개 지정한다.

재귀함수 dfs를 사용해서 결과를 도출해냄.

코드

n, m = map(int,input().split())
graph = [[] for  _ in range(n)]
visited = [False] * 2001
result = False

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

def dfs(idx, number):
  global result
  visited[idx] = True
  if number == 4:
    result = True
    return
  for i in graph[idx]:
    if not visited[i]:
      visited[i] = True
      dfs(i, number+1)
      visited[i] = False
      
for i in range(n):
  dfs(i, 0)
  visited[i] = False
  if result:
    break
if result:
  print(1)
else:
  print(0) 

결과