[백준 13023] ABCDE

문제

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

 

코드 

import sys
from collections import deque
sys.setrecursionlimit(10**9)

def Input_Data():
    input = sys.stdin.readline
    N, M = map(int, input().strip().split())
    adj = {i : [] for i in range(N)}
    for _ in range(M):
        a, b = map(int, input().strip().split())
        adj[a].append(b)
        adj[b].append(a)
    return N, M, adj

def Dfs(start, depth):
    global isFriend 
    visited[start] = True 
    if depth == 4: # 조건을 만족함 -> 5명의 친구 관계 찾음 
        isFriend = True
        return
    for x in adj[start] : 
        if visited[x] == 0: 
            visited[x] = True
            Dfs(x, depth+1)
            if isFriend : return #이미 찾았으면 더 이상 반복하지 않음 
    visited[start] = False # 다른 경로에서는 반복 x --> 백트래킹: 다시 방문 할 수 있도록 

N, M, adj = Input_Data()
visited = [0] * (N)
isFriend = False
for i in range(N):
    Dfs(i, 0)
    if isFriend : break
if isFriend : print(1)
else: print(0)