[백준] 13023번 - ABCDE

문제 분석

문제를 읽어보면 알 수 있듯이 서로의 관계의 길이가 5이상인 경우를 찾으면 된다는 것을 알 수 있다.
따라서 서로의 관계를 표현할 때에는 인접리스트의 형식으로 표현하고, 해당 관계들을 DFS를 사용하여, 관계의 길이가 5이상인 경우를 찾아내면 된다.
문제에서 N의 최대 범위가 2,000이고, DFS의 시간복잡도는 O(V+E)이므로 최대 4,000, 모든 노드를 진행했을때에는 4,000 * 2,000,
즉 8,000,000이므로 2초(== 약 4천만)안에 문제를 풀 수 있다.

소스 코드

# ABCDE

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
visit = [False]*(N+1)
success = False


def recursion(idx, count):
    global success

    if count == 5:
        success = True
        return

    visit[idx] = True
    for value in arr[idx]:
        if not visit[value]:
            recursion(value, count + 1)
    visit[idx] = False


for _ in range(M):
    firstNode, secondNode = map(int, input().split())
    arr[firstNode].append(secondNode)
    arr[secondNode].append(firstNode)


for i in range(N):
    recursion(i, 1)
    if success:
        break

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