백준 13023번: ABCDE(Python, 파이썬, DFS, 백트래킹)

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.

• B는 C와 친구다.

• C는 D와 친구다.

• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

[BOJ 13023] ABCDE — DFS로 “5명 짜리 친구 사슬” 찾기

백준 13023번 ABCDE 문제는 겉으로 보면 단순한 그래프 문제처럼 보이는데,
솔직히 말해서 문제 설명이 꽤 불친절하다.

처음 읽었을 땐 나는 이렇게 이해했다:

“그래프에 있는 모든 노드가 하나의 컴포넌트로 이어져 있는지 묻는 문제인가?”

근데 알고 보니 전혀 아니었다 😅
실제로는,

친구 관계로 이어진 “서로 다른 5명”만 하나라도 존재하면 끝나는 문제다.

이건 나도 직접 검색(질문/풀이 글 등)을 해보고 나서야
“아, 아~ 이게 그 경로 길이 4(정점 5개) 찾기 문제구나” 하고 제대로 이해했다.

그래서 이 글에서는:

1. 문제를 내가 이해한 방식대로 다시 정리하고

2. DFS로 푸는 아이디어

3. 시간 복잡도

4. 로직 순서에 따른 코드 해설

5. 마지막에 전체 코드

까지 정리해서 남겨본다.

1. 문제 다시 정리하기 (내 말로)

• 사람 수: N (0 ~ N-1번)

• 친구 관계 수: M

• u v 가 주어지면 u와 v는 친구 (양방향 간선)

문제가 묻는 건 딱 하나:

서로 다른 사람 5명 A-B-C-D-E가 있어서
A는 B의 친구, B는 C의 친구, C는 D의 친구, D는 E의 친구인 경우가
한 번이라도 존재하는가?

그래프 용어로 바꾸면:

• 정점 5개가 연속으로 이어진 단순 경로(simple path)가 있는지 확인하는 문제다.

• 이게 있으면 1, 없으면 0을 출력한다.

“그래프가 한 덩어리로 다 연결되었냐”를 묻는 문제가 절대 아니다.
“길이가 4(정점 5개)인 경로가 하나라도 있냐”가 핵심이다.

2. 접근 방법: DFS로 깊이 5까지 탐색

아이디어는 간단하다.

1. 사람 하나를 시작점으로 잡고

2. DFS로 친구 관계를 타고 최대 깊이 5(= 사람 5명)까지 내려가 본다.

3. 중간에 서로 다른 사람 5명을 연속으로 방문하면 바로 1을 출력하고 종료.

4. 어떤 시작점에서도 그런 경로를 찾지 못하면 0 출력.

왜 DFS인가?

• “연속된 사람들”을 따라가며 경로를 하나씩 뻗어가보기 좋은 게 DFS다.

• 그리고 경로 길이가 5명에서 끊기 때문에,
  탐색 깊이가 매우 제한적이라 실제로는 많이 돌지 않는다.

방문 체크(visited)

• 한 경로에서 같은 사람을 두 번 방문하면 안 되므로 visited 배열을 사용한다.

• 시작 노드를 하나 정할 때마다 visited를 새로 초기화해주고,

• DFS 안에서 방문했다가, 재귀가 끝나면 다시 False로 돌려놓는 방식(backtracking)으로 쓴다.

3. 시간 복잡도

• 그래프는 인접 리스트로 저장한다: graphs[u]에 u의 친구 목록.

• 각 정점마다 DFS를 한 번씩 돌리는데,

  • DFS 깊이는 최대 5 (count가 5가 되면 바로 종료)

  • 중복 방문을 막아서 “무한”으로 퍼지지 않는다.

실질적으로는:

• 각 노드에서 최대 깊이 5까지의 경로만 탐색

• 간선 수 M이 20만까지여도, 깊이 제한이 있어서 충분히 통과되는 유명한 풀이 패턴이다.

대략적으로는:

시작점 N개 × (깊이 5인 DFS) → O(N + M) 수준에서 동작한다고 볼 수 있다.
(정확히 따지면 분기 수에 따라 상수는 달라지지만, 제한 내에서 충분히 빠르다.)

4. 로직 순서에 따른 자세한 해설

이제 내가 짠(혹은 가져온) 코드를 기준으로 차근차근 뜯어보자.

import sys
from collections import deque

sys.setrecursionlimit(10**8)

• sys.stdin.readline()을 빠르게 쓰기 위해 sys를 import.

• 재귀 DFS를 쓰기 때문에, 최악의 경우를 대비해서 recursionlimit을 크게 늘려준다.

• deque는 이 코드에서는 안 쓰지만, BFS를 시도하다 남겨둔 흔적처럼 보인다. (지워도 무방)

4-1. 입력 & 그래프 구성

N, M = map(int,sys.stdin.readline().split())

graphs = [[] for _ in range(N)]

for _ in range(M):
    u, v = map(int,sys.stdin.readline().split())
    graphs[u].append(v)
    graphs[v].append(u)

• N: 사람 수, M: 친구 관계 수

• graphs: 크기 N짜리 리스트, 각 인덱스에 그 사람의 친구 목록을 저장

• 친구 관계는 양방향이므로

  • graphs[u]에 v 추가

  • graphs[v]에 u 추가

즉, 무방향 그래프의 인접 리스트를 만드는 부분이다.

4-2. DFS 함수

def dfs(friend_number, count):
    global visited
    
    if count == 5:
        print(1)
        exit()
    # graph[i] 가 일단 존재하는가?
    if graphs[friend_number] :
        for next_friend in graphs[friend_number]:
            if not visited[next_friend]:
                visited[next_friend] = True
                count += 1
                dfs(next_friend, count)
                count -= 1
                visited[next_friend] = False

인자 설명

• friend_number
  → 지금 보고 있는 사람(노드)의 번호

• count
  → 지금까지 이어진 사람 수 (현재 노드 포함)

종료 조건

if count == 5:
    print(1)
    exit()

• 만약 이미 5명을 연속으로 방문했다면, 조건을 만족한 것이므로

• 바로 1을 출력하고 프로그램을 종료한다.

• 더 이상 다른 경로를 탐색할 필요가 없다.

인접 노드 탐색

if graphs[friend_number]:
    for next_friend in graphs[friend_number]:
        if not visited[next_friend]:
            visited[next_friend] = True
            count += 1
            dfs(next_friend, count)
            count -= 1
            visited[next_friend] = False

• graphs[friend_number]가 비어있지 않다면,
  즉, 이 사람에게 친구가 있다면 그 친구들을 하나씩 방문해 본다.

• 아직 방문하지 않은 next_friend에 대해서만:

  1. visited[next_friend] = True → 경로에 포함시키고

  2. count += 1 → 사람 수 하나 늘리고

  3. 재귀 호출 dfs(next_friend, count)

  4. 돌아와서는 count -= 1, visited[next_friend] = False
     → 다른 경로 탐색을 위해 원상복구(backtracking)

이렇게 하면 “서로 다른 사람들로만 이루어진 경로”들만 탐색하게 된다.

4-3. 모든 시작점에서 DFS 돌리기

for i in range(N):
    visited = [False for _ in range(N)]
    visited[i] = True
    dfs(i,1)

print(0)

• 모든 사람(i)을 시작점으로 한 번씩 DFS를 돌린다.

• 각 시작점마다:

  • visited 배열을 새로 만든다.

  • 시작 노드 i를 방문했다고 표시: visited[i] = True

  • dfs(i, 1) 호출 → 지금까지 이어진 사람 수는 1명 (자기 자신)

DFS 도중에 어느 시점에서든 5명 경로를 찾으면 print(1); exit()로 프로그램이 끝나기 때문에,
여기까지 코드가 내려왔다는 건 5명짜리 경로가 어디에도 없었다는 뜻이다.

그래서 마지막 줄에서:

print(0)

을 출력하며 종료한다.

5. 전체 코드

마지막으로, 위에서 설명한 내용을 모두 포함한 전체 코드를 한 번에 정리하면 아래와 같다.

import sys
from collections import deque

sys.setrecursionlimit(10**8)

N, M = map(int, sys.stdin.readline().split())

graphs = [[] for _ in range(N)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graphs[u].append(v)
    graphs[v].append(u)


def dfs(friend_number, count):
    global visited

    # 5명이 연속으로 이어졌다면 조건 만족
    if count == 5:
        print(1)
        exit()

    # 현재 사람에게 친구가 있다면, 하나씩 탐색
    if graphs[friend_number]:
        for next_friend in graphs[friend_number]:
            if not visited[next_friend]:
                visited[next_friend] = True
                count += 1
                dfs(next_friend, count)
                count -= 1
                visited[next_friend] = False


# 모든 사람을 시작점으로 삼아 DFS 시도
for i in range(N):
    visited = [False for _ in range(N)]
    visited[i] = True
    dfs(i, 1)

# 끝까지 못 찾으면 0
print(0)