[BOJ] 13023번: ABCDE

■ 문제 풀이

그래프의 길이가 4 이상인 경우 조건 충족 (1)

시작하는 지점이 다를 경우 값 또한 달라지므로 완전 탐색으로 진행

dfs를 이용하여 풀이 진행

■ 문제 해답

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

# 리스트 행렬
graph = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [False] * n

ans = False
# 깊이 탐색 진행
def dfs(v, depth):
  global ans
  if depth == 4:
    ans = True
    return

  for i in graph[v]:
    if not visited[i]:
      visited[i] = True
      dfs(i, depth + 1)
      visited[i] = False

# 각 정점마다 완전탐색 진행 (깊이가 4 이상인 경우)
for i in range(n):
  visited[i] = True
  dfs(i, 0) # 완전 탐색 진행 후 방문 여부 False로 전환
  visited[i] = False
  if ans:
    break

if ans:
  print(1)
else:
  print(0)

문제출처: https://www.acmicpc.net/problem/13023

13023번: ABCDE