[알고리즘] DFS 백트래킹 vs 오일러 경로 (Hierholzer 알고리즘)

프로그래머스 여행경로 문제를 풀면서 정리한 그래프 경로 탐색 이론. 같은 문제를 DFS 백트래킹과 오일러 경로 두 가지 방식으로 풀어보면서 차이를 비교했다.

---

1. DFS 백트래킹

핵심 아이디어

선택 → 탐색 → 실패하면 선택 취소 → 다른 선택 시도

막히면 되돌아가서 다른 경로를 시도하는 방식이다. "정답인지 모르는 상태로 일단 가보고, 틀리면 지우고 다시 쓴다."

기본 구조

def dfs(start):
    if 종료조건:
        return True

    for 선택지 in 후보들:
        if 사용가능:
            선택()              # 사용 처리
            
            if dfs(다음_노드):
                return True     # 성공하면 위로 전파
            
            선택취소()          # 실패하면 되돌리기

    return False

세 단계로 요약하면 선택 → 재귀 → 취소다. 이 패턴이 백트래킹의 전부라고 봐도 무방하다.

여행경로 문제 적용

from collections import defaultdict

def solution(tickets):
    answer = ["ICN"]
    graph = defaultdict(list)
    for k, v in tickets:
        graph[k].append(v)

    for key in graph:
        graph[key].sort()             # 알파벳 오름차순

    def dfs(start):
        if len(answer) == len(tickets) + 1:
            return True

        for i in range(len(graph[start])):
            next_node = graph[start].pop(i)
            answer.append(next_node)

            if dfs(next_node):
                return True

            graph[start].insert(i, next_node)  # 원상복구
            answer.pop()

    dfs("ICN")
    return answer

주의할 점: 원상복구는 "같은 자리"에

처음에 sort(reverse=True) + pop() + append() 조합으로 시도했다가 무한루프에 빠진 적이 있다.

graph["ICN"] = ["SFO", "ATL"]   # reverse=True 상태

pop() → "ATL" 꺼냄
실패 → append("ATL") → ["SFO", "ATL"]   # 원상복구
pop() → 또 "ATL" ← 무한루프!

append()는 항상 맨 뒤에 추가하기 때문에, pop()으로 마지막 요소를 꺼내는 구조와 맞물리면 같은 노드가 계속 반복된다.

해결법은 pop(i) + insert(i, node) 조합이다. 꺼낸 자리 그대로 돌려놓아야 무한루프 없이 다음 인덱스로 넘어갈 수 있다.

next_node = graph[start].pop(i)    # i번째에서 꺼냄
...
graph[start].insert(i, next_node)  # i번째에 그대로 복구

백트래킹이 "이전 호출"로 돌아가는 원리

dfs(next_node)가 False를 반환하면, 그 호출을 시작한 for문의 다음 인덱스로 돌아간다. 맨 처음으로 돌아가는 게 아니라, 콜스택을 한 단계씩 거슬러 올라가는 것이다.

dfs("ICN")          ← i=0에서 dfs("ATL") 호출
  dfs("ATL")        ← i=0에서 dfs("ICN") 호출
    dfs("ICN")      ← i=0에서 dfs("SFO") 호출
      dfs("SFO")    ← 갈 곳 없음 → False
    ← False 받음, 원상복구, i=1로 이동

시간복잡도

구분 복잡도 근거

최악의 경우	O(N * N!)	모든 순열을 시도할 수 있음
실제 동작	훨씬 빠름	알파벳 오름차순 정렬 덕분에 첫 성공 경로에서 즉시 종료

---

2. 오일러 경로 (Hierholzer 알고리즘)

핵심 아이디어

막힌 노드는 무조건 경로의 끝이다.

DFS처럼 선택을 취소하며 되돌아가는 게 아니라, 막힌 노드를 먼저 확정하고 마지막에 뒤집는 방식이다.

왜 "막힌 노드 = 끝"이 보장되는가

이 알고리즘은 모든 간선(티켓)을 반드시 사용해야 한다는 조건이 있을 때만 성립한다.

나가는 간선이 없는 노드는 그래프 구조상 어떤 경로를 그리든 항상 마지막일 수밖에 없다. 즉 "이 노드가 맞는 선택인지"를 따질 필요 자체가 없다. 막혔다는 사실 자체가 곧 "여기가 끝"이라는 증명이 된다.

DFS는 선택이 맞는지 모르기 때문에 백트래킹이 필요하지만, 오일러 경로는 막히는 순간 그 자체가 정답의 일부로 확정되므로 되돌아갈 필요가 없다.

기본 구조

def euler_path(graph, start):
    stack = [start]
    path = []

    while stack:
        top = stack[-1]

        if graph[top]:                     # 갈 곳이 있으면
            stack.append(graph[top].pop())  # 전진
        else:                              # 막히면
            path.append(stack.pop())       # 확정

    return path[::-1]                      # 뒤집어서 반환

여행경로 문제 적용

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]

    for r in routes:
        routes[r].sort(reverse=True)   # pop()으로 오름차순 꺼내기 위해 역정렬

    stack = ["ICN"]
    path = []

    while stack:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[top].pop())

    return path[::-1]

스택이 "되돌아가기"를 대신하는 원리

DFS는 막히면 명시적으로 선택을 취소(pop, insert)해야 한다. 오일러 경로는 그럴 필요가 없다. 이유는 스택 자체가 지나온 경로를 그대로 기억하고 있기 때문이다.

stack = ["ICN", "A", "ICN", "B"]
                              ↑
                    지금 서 있는 위치 (stack[-1])

B가 막히면 B를 꺼내 path에 확정한다. 그 순간 스택의 맨 위는 자동으로 B 이전 위치인 ICN이 된다. 선택을 취소한 게 아니라, 이미 쌓여 있던 발자국을 따라 자연스럽게 이전 위치로 돌아간 것이다.

막힌 곳이 여러 군데여도 마찬가지다. 한 곳이 막히면 스택이 자동으로 그 이전 분기점으로 복귀시켜주기 때문에, 별도의 복구 로직 없이도 전체 경로가 정확히 완성된다.

시간복잡도

구분 복잡도 근거

전체

O(N)

모든 간선을 정확히 한 번씩만 방문

DFS 백트래킹과 비교하면 압도적으로 빠르다.

---

3. 두 방식 비교

DFS 백트래킹 오일러 경로

핵심 발상	틀린 선택을 지우고 되돌아가기	막힌 노드를 끝으로 확정
확정 방향	앞에서부터	뒤에서부터 (뒤집기)
구현 방식	재귀	while + 명시적 stack
되돌아가는 방법	pop(i) + insert(i)로 명시적 복구	스택에 남은 경로를 그대로 활용
시간복잡도	O(N * N!)	O(N)
직관성	높음	낮음
여러 경로 반환	가능	불가능 (경로 하나만 보장)
코테 빈출도	높음	낮음

정리

• 오일러 경로는 "경로가 정확히 하나로 보장될 때" 만 쓸 수 있다. 즉 "모든 간선을 반드시 사용해야 한다"는 조건이 핵심 전제다.
• 이 조건이 없거나 여러 경로를 모두 찾아야 한다면 DFS 백트래킹이 필요하다.
• 코딩테스트에서는 DFS 백트래킹을 우선적으로 떠올리는 게 현실적이다. 오일러 경로는 발상 자체가 직관적이지 않아 현장에서 처음 떠올리기 어렵다.
• 다만 "막힌 노드는 무조건 끝" 이라는 핵심 통찰은 그래프 문제를 바라보는 시야를 넓혀준다.

DFS는 메모장을 들고 다니며 틀린 길을 지우는 방식이고, 오일러 경로는 빵가루를 떨어뜨리며 발자국을 따라 자연스럽게 돌아오는 방식이다.