[BOJ/백준] 13023 ABCDE

def dfs(i,cnt):
    global result
    visited[i] = False
    if cnt >= 5:
        result = True
        return
    for ind in graph[i]:
        if visited[ind]:
            dfs(ind,cnt+1)
    visited[i] = True
 
 
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
 
 
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
 
visited = [True]*N
result = False
for i in range(N):
    dfs(i,1)
    if result:
        break
print(int(result))

DFS를 해서 깊이가 4 이상이면 True를 반환해주면 되는 문제이다.

 

위와 같이 재귀를 해서 풀어도 되고, 

 

 

import sys
input = sys.stdin.readline
def solution():
    global N
    for dep0 in range(N):
        for dep1 in graph[dep0]:
            for dep2 in graph[dep1]:
                if dep0 == dep2:
                    continue
                for dep3 in graph[dep2]:
                    if dep3 == dep1 or dep3 == dep0:
                        continue
                    for dep4 in graph[dep3]:
                        if dep4 != dep0 and dep4 != dep1 and dep4 != dep2:
                            return 1
    return 0
 
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
 
print(solution())

깊이가 그리 깊지 않으니 하드코딩으로 분기처리를 해주어도 풀 수 있다.