[백준] 13023 ABCDE

🔗 문제 링크

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

💻 코드

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

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)
result = 0
visited = [0] * n


def dfs(start,cnt):
    global result

    if cnt == 5:
        result = 1
        return
        
    visited[start] = 1
    
    for node in graph[start]:
        if not visited[node]:
            dfs(node,cnt+1)

    visited[start] = 0
    return

for i in range(n):
    dfs(i,1)
    if result:
        break


print(result)

🤷‍♂ 풀이

• 친구관계 그래프에서 연속된 5명의 친구관계가 존재하는지 확인하는 문제이다.

• 인접 리스트 방식으로 친구 관계를 추가한다.

• cnt == 5 (연결된 5명)이면 result = 1 후 종료

• 탐색 후 visited[start] = 0으로 방문 해제 → 다른 경로 탐색 가능

• 모든 노드에서 탐색을 시작한다.

• 최악의 경우 모든 노드에서 DFS를 시작하므로 O(n^2)이다.