오일러 경로와 오일러 회로

오일러 경로와 회로

오일러 경로(Eulerian path) 는 그래프의 모든 간선을 정확히 한 번씩 지나는 경로다. 시작점과 끝점이 같으면 오일러 회로(Eulerian circuit) 다. 한붓 그리기 문제이고, 쾨니히스베르크 다리 문제에서 출발했다.

BFS·DFS가 정점을 한 번씩 방문하는 데 비해, 오일러 경로는 간선을 한 번씩 쓴다. 그래서 방문 체크도 정점이 아니라 간선에 한다. 정점은 여러 번 지나도 된다. 모든 정점을 한 번씩 지나는 해밀턴 경로는 이름이 비슷하지만 NP-완전으로, 전혀 다른 문제다.

존재 조건

간선이 있는 정점들이 모두 하나의 연결 요소에 속한다는 전제에서, 조건은 차수의 짝홀만으로 정해진다.

이유는 간단하다. 회로에서 어떤 정점에 들어오면 반드시 다른 간선으로 나가야 하므로, 간선이 들어오고 나가는 짝을 이룬다. 그래서 차수가 짝수여야 한다. 조건을 먼저 검사하면 불가능한 입력을 바로 걸러 낼 수 있다.

히어홀저 알고리즘

히어홀저(Hierholzer) 알고리즘은 DFS로 간선을 지우며 나아가다가, 더 갈 간선이 없는 정점에서 되돌아올 때 그 정점을 결과에 붙인다. 이렇게 모은 순서를 뒤집으면 오일러 회로다.

1. 아무 정점(경로라면 홀수 차수 정점)에서 시작한다.
2. 현재 정점에 남은 간선이 있으면 하나를 지우고 그쪽으로 간다.
3. 남은 간선이 없으면 현재 정점을 결과에 추가하고 한 단계 되돌아간다.
4. 결과를 뒤집는다. (무방향 회로라면 뒤집지 않아도 역방향 회로다)

먼저 간 길이 막다른 곳에 일찍 닿아도 괜찮다. 되돌아오는 도중 남은 간선이 있는 정점에서 다시 들어가 작은 회로를 만들고, 그 회로가 후위 순서 덕분에 올바른 자리에 끼워진다.

def euler_circuit(n, edges, start=0):
    graph = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):      # 간선마다 번호를 붙여 다중 간선도 구분
        graph[u].append((v, i))
        graph[v].append((u, i))
    if any(len(adj) % 2 for adj in graph):  # 홀수 차수 정점이 있으면 회로 없음
        return None
 
    used = [False] * len(edges)
    ptr = [0] * n                           # 정점마다 "다음에 볼 간선" 위치
    stack, circuit = [start], []
    while stack:
        v = stack[-1]
        while ptr[v] < len(graph[v]) and used[graph[v][ptr[v]][1]]:
            ptr[v] += 1                     # 이미 쓴 간선은 다시 보지 않는다
        if ptr[v] == len(graph[v]):
            circuit.append(stack.pop())     # 막혔다 → 결과에 붙이고 되돌아감
        else:
            nxt, eid = graph[v][ptr[v]]
            used[eid] = True
            stack.append(nxt)
    return circuit[::-1]
 
print(euler_circuit(5, [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]))
# [0, 1, 2, 0, 3, 4, 0]

재귀 대신 명시적 스택을 썼다. 간선이 수십만 개면 재귀 깊이가 간선 수만큼 깊어지기 때문이다.

시간 초과를 피하는 요령

교과서식 재귀 구현은 인접 행렬에서 매 호출마다 모든 정점을 처음부터 훑어 남은 간선을 찾는다. 간선을 지울수록 빈칸만 계속 훑으므로 정점 V, 간선 E일 때 O(V × E)까지 느려진다. 정점이 1000개이고 정점 쌍마다 간선이 여러 개인 입력에서 이 차이가 시간 초과를 가른다.

모두 "한 번 쓴 간선은 다시 비용을 내지 않는다"는 원칙이다. 그러면 전체가 O(V + E)가 된다.

정리

• 오일러 경로·회로는 정점이 아니라 간선을 한 번씩 지난다.
• 무방향 회로는 모든 차수가 짝수, 경로는 홀수 차수 정점이 0개 또는 2개 (연결 전제)
• 히어홀저: 간선을 지우며 DFS, 막히면 후위 순서로 기록하고 뒤집는다.
• 정점별 포인터와 간선 번호로 이미 쓴 간선을 다시 훑지 않으면 O(V + E)다.

관련 노트: DFS, 그래프의 기본, 단절점과 단절선