12.2 완전 경로

참조

도서

• 안티 라크소넨, 『알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드』, 인사이트, 2022, p.242

영상

• • 시청 필수가 아님. 참고를 위해 단 것

그래프 기본

• 그래프

완전 경로

그래프의 경로와 관련된 중요한 개념 두 가지를 살펴본다. 오일러 경로는 모든 간선을 정확히 한 번씩 지나는 경로이고, 해밀턴 경로는 모든 노드를 정확히 한 번씩 방문하는 경로이다. 언뜻 봐서는 유사한 개념이라고 생각하기 쉽지만, 이와 관련된 계산 문제는 매우 다르다.

오일러 경로

**오일러 경로(Eulerian path)**는 그래프의 각 간선을 정확히 한 번씩 지나는 경로이다. 그러한 경로의 시작과 끝이 같은 노드인 경우를 **오일러 회로(Eulerian circuit)**라고 부른다. 그림 9에 2번 노드에서 시작하여 5번 노드에서 끝나는 오일러 경로가 나와 있고, 그림 10에는 1번 노드에서 시작하고 끝나는 오일러 회로가 나와 있다.

• 그림 9. 그래프와 오일러 경로

  • 

• 그림 10. 그래프와 오일러 회로

  • 

무방향 그래프에서

오일러 경로와 오일러 회로가 존재하는지는 노드의 차수에 따라 결정된다. 먼저, 무방향 그래프에 오일러 경로가 있는 경우는 모든 간선이 같은 연결 컴포넌트에 속하고 다음 두 조건 중 하나를 만족하는 경우와 동치이다.

• 모든 노드의 차수가 짝수이거나,
• 정확히 두 노드의 차수가 홀수이고, 다른 모든 노드의 차수는 짝수이다.

첫 번째 경우, 오일러 경로는 곧 오일러 회로가 된다. 두 번째 경우, 차수가 홀수인 두 노드가 오일러 경로의 양 끝점이 되며 이때는 오일러 회로가 아니다. 그림 9의 그래프에서 1, 3, 4번 노드의 차수는 2이고, 2, 5번 노드의 차수는 3이다. 정확히 두 노드의 차수가 홀수이므로 2번 노드와 5번 노드가 양 끝점인 오일러 경로가 존재하며 오일러 회로는 존재하지 않는다. 그림 10의 그래프는 모든 노드의 차수가 짝수이므로 오일러 회로가 존재한다.

방향 그래프에서

방향 그래프에 오일러 경로가 존재하는지를 확인하기 위해서는 노드의 진입 차수와 진출 차수를 확인하면 된다. 방향 그래프에 오일러 경로가 존재하는 경우는 모든 간선이 같은 강결합 컴포넌트에 속하고 다음 두 조건 중 하나를 만족하는 경우와 동치이다. ¹

• 모든 노드의 진입 차수와 진출 차수가 같거나,
• 한 노드의 진입 차수가 진출 차수보다 1 크고, 다른 한 노드의 진출 차수가 진입 차수보다 1 크며, 나머지 노드는 진입 차수와 진출 차수가 같다.

첫 번째 경우, 오일러 경로는 곧 오일러 회로가 된다. 두 번째 경우, 진출 차수가 큰 노드에서 시작해서 진입 차수가 큰 노드에서 끝나는 오일러 경로가 존재한다. 예를 들어 그림 11의 그래프에서 1, 3, 4번 노드의 진입 차수와 진출 차수는 모두 1이고, 2번 노드는 진입 차수가 1이고 진출 차수가 2이며, 5번 노드는 진입 차수가 2이고 진출 차수가 1이다. 그러므로 이 그래프에는 2번 노드에서 시작해서 5번 노드에서 끝나는 오일러 경로가 존재한다.

• 그림 11. 방향 그래프와 오일러 경로
  • 

경로 찾기

**히어홀처 알고리즘(Hierholzer’s algorithm)**은 그래프의 오일러 회로를 찾는 효율적인 방법이다. 이 알고리즘은 여러 단계로 구성되어 있으며, 단계마다 회로에 새로운 간선을 추가한다. 물론 그래프에 오일러 회로가 있다고 가정하며, 그렇지 않은 경우엔 오일러 회로를 찾을 수 없다.

노드가 하나 있고 간선이 없는 빈 회로에서 알고리즘을 시작하고, 부분 회로를 추가하는 식으로 회로를 한 단계씩 확장해 나간다. 이 과정을 모든 간선이 회로에 추가될 때까지 진행한다. 회로를 확장하기 위해서는 회로에 속한 노드 중 회로에 포함되지 않은 진출 간선이 있는 노드 $x$를 찾는다. 그리고 노드 $x$에서 시작하여 아직 회로에 포함되지 않은 간선으로 이루어진 경로를 구성한다. 언젠가는 이 경로가 노드 $x$로 돌아오게 되는데, 이 경로가 부분 회로가 된다.

그래프에 오일러 회로는 없지만 오일러 경로가 있는 경우에도 히어홀처 알고리즘을 적용할 수 있는데, 새로운 간선을 그래프에 추가하고 오일러 회로를 찾은 뒤, 그 간선을 제거하면 된다. 예를 들어 무방향 그래프에서는 차수가 홀수인 두 노드를 잇는 새로운 간선을 추가하면 된다. (오일러 경로가 가능한 홀수 차수 그래프에서, 홀수 노드 간에 간선을 추가하여 오일러 회로로 만든다. 그리고 추가한 간선을 제거한다)

• 그림 12. 히어홀처 알고리즘
  • 

그림 12에 히어홀처 알고리즘을 적용하여 무방향 그래프에서 오일러 회로를 찾는 과정의 예가 나와 있다. 먼저 부분 회로 $1\to 2\to 3\to 1$을 추가하고, 다음으로 부분 회로 $2\to 5\to 6\to 2$를 추가하며, 마지막으로 부분 회로 $6\to 3\to 4\to 7\to 6$을 추가한다. 그러면 모든 간선이 회로에 추가되었으므로, 최종 결과는 오일러 회로가 된다.

• 꼭 작은 사이클을 포함하면서 가는 방법이 아니여도 동작한다.
• $1\to 2\to 5\to 6\to 3\to 4\to 7\to 6\to 2\to 3\to 1$

절차 - 무방향 그래프

•   0. 이론적 조건
       - 간선이 있는 모든 정점이 하나의 연결 컴포넌트에 있어야 한다.
       - 홀수 차수 정점 개수가 0개 또는 2개여야 한다.
    1. 시작 정점을 정한다.
       - 홀수 차수 정점이 0개: 오일러 회로 → 간선이 있는 아무 정점
       - 홀수 차수 정점이 2개: 오일러 경로 → 홀수 차수 정점 중 하나
    2. 현재 정점에서 아직 사용하지 않은 간선을 하나 고른다.
    3. 그 간선을 삭제하고 다음 정점으로 이동한다.
    4. 더 이상 갈 간선이 없으면 현재 정점을 path에 넣는다.
    5. DFS가 끝난 뒤 path를 뒤집으면 정답 경로가 된다.

절차 - 방향 그래프

•   0. 이론적 조건
       - 간선이 있는 모든 정점이 방향을 무시했을 때 하나의 연결 컴포넌트에 있어야 한다.
       - 오일러 회로:
         모든 정점에 대해 in[v] == out[v]
       - 오일러 경로:
         시작점 start 하나는 out[start] = in[start] + 1
         끝점 end 하나는 in[end] = out[end] + 1
         나머지 정점은 in[v] == out[v]
    1. 시작 정점을 정한다.
       - 오일러 회로: out[v] > 0인 아무 정점
       - 오일러 경로: out[start] = in[start] + 1 인 정점
    2. 현재 정점에서 아직 사용하지 않은 "나가는 간선"을 하나 고른다.
    3. 그 방향 간선을 삭제하고 다음 정점으로 이동한다.
    4. 더 이상 나가는 간선이 없으면 현재 정점을 path에 넣는다.
    5. DFS가 끝난 뒤 path를 뒤집으면 정답 경로가 된다.

참고

• [그래프] 오일러 회로 | JusticeHui가 PS하는 블로그
  • 절차 참고
• [Algorithm] 오일러 경로 — AlgorFati의 개발 기록
  • 다음 이미지 이후로 dfs 과정 참고
  • 

연습 문제

• 1199번: 오일러 회로
• 3485번: Play on Words

해밀턴 경로

**해밀턴 경로(Hamiltonian path)**는 그래프의 모든 노드를 정확히 한 번씩만 방문하는 경로이다. 이 경로의 시작 노드와 마지막 노드가 같은 경우는 **해밀턴 회로(Hamiltonian circuit)**라고 부른다. 예를 들어 그림 13에 해밀턴 경로와 해밀턴 회로가 모두 있는 그래프가 나와 있다.

• 그림 13. 그래프, 해밀턴 경로, 해밀턴 회로
  • 

해밀턴 경로와 관련된 문제는 NP-하드이다. 그래프에 해밀턴 경로나 해밀턴 회로가 있는지를 효율적으로 찾는 일반적인 방법은 알려지지 않았다. 물론 몇몇 특별한 경우에는 그래프에 항상 해밀턴 경로가 있음을 보장할 수 있다. 예를 들어 완전 그래프, 즉 모든 노드 간에 간선이 있는 그래프에는 당연히 해밀턴 경로가 존재한다.

해밀턴 경로를 찾는 간단한 방법은 퇴각 검색 알고리즘을 이용하여 경로를 구성하는 모든 가능한 경우를 탐색하는 것이다. 이때 노드 $n$개를 방문하는 순서가 $n!$가지 존재하므로, 알고리즘의 시간 복잡도는 최소 $O(n!)$이 된다.

동적 계획법을 이용하면 좀 더 효율적인 $O(2^n{n}^2)$ 시간에 해를 찾을 수 있다(Held–Karp algorithm - Wikipedia). 노드의 모든 부분집합 $S$와 $x\in S$인 모든 노드 $x$에 대해, $S$의 모든 노드를 정확히 한 번씩만 방문하고 노드 $x$에서 끝나는 경로가 있는지를 확인해 보는 것이다.

연습문제

• 해밀턴 순환회로2 - JUNGOL | TSP

• 시간 복잡도

  • $O(N^2\times 2^N)$
  • $N$ 16 ~ 18 일때 가능
    • 현재 도시 cur의 경우의 수: $N$
    • 방문 상태 mask의 경우의 수: $2^N$
    • 다음 도시 next 탐색: $N$

• dp[mask][u]

  • 그 상태에 도달하는 여러 경우 중, u 가 마지막 도시인 경우의 최소 값
  • dp[01101][2]
    • 다음 경우들을 포함한 상태
    • 0 → 3 → 2
    • 3 → 0 → 2

연습 코드

cpp

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO \
ios::sync_with_stdio(false); \
cin.tie(nullptr);
 
int main() {
    FAST_IO;
 
    int n;
    cin >> n;
 
    vector<vector<int>> w(n, vector<int>(n));
 
    // TODO 1. 비용 행렬 입력받기
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> __________;
        }
    }
 
    const int INF = 1e9;
 
    // full은 전체 방문 상태의 개수
    // n개의 도시가 있으면 가능한 방문 상태는 2^n개
    int full = __________;
 
    // dp[mask][u]
    // mask 상태로 도시들을 방문했고, 현재 u번 도시에 있을 때의 최소 비용
    vector<vector<int>> dp(full, vector<int>(n, INF));
 
    // 출발 도시는 0번 도시
    // 0번 도시만 방문한 상태는 mask = 1
    dp[__________][__________] = 0;
 
    // TODO 2. 모든 방문 상태를 순회한다
    for (int mask = 1; mask < full; ++mask) {
 
        // TODO 3. 현재 마지막 도시 u를 순회한다
        for (int u = 0; u < n; ++u) {
 
            // 아직 도달할 수 없는 상태라면 건너뛴다
            if (dp[mask][u] == __________) {
                continue;
            }
 
            // TODO 4. 다음에 방문할 도시 v를 고른다
            for (int v = 0; v < n; ++v) {
 
                // 이미 방문한 도시이거나, u -> v 길이 없으면 건너뛴다
                if ((mask & (__________)) || w[u][v] == 0) {
                    continue;
                }
 
                // TODO 5. v를 방문한 새로운 상태를 만든다
                int nxt = mask | __________;
 
                // TODO 6. dp 갱신
                dp[nxt][v] = min(
                    dp[nxt][v],
                    ________________________________
                );
            }
        }
    }
 
    int ans = INF;
 
    // 모든 도시를 방문한 상태
    int all_visited = full - 1;
 
    // TODO 7. 마지막 도시 u에서 다시 0번 도시로 돌아오는 비용을 더한다
    for (int u = 1; u < n; ++u) {
        if (w[u][0] != 0) {
            ans = min(
                ans,
                ________________________________
            );
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}

python

import sys
input = sys.stdin.readline
 
n = int(input())
 
w = [[0] * n for _ in range(n)]
 
# TODO 1. 비용 행렬 입력받기
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        w[i][j] = __________
 
INF = 10 ** 9
 
# full은 전체 방문 상태의 개수
# n개의 도시가 있으면 가능한 방문 상태는 2^n개
full = __________
 
# dp[mask][u]
# mask 상태로 도시들을 방문했고, 현재 u번 도시에 있을 때의 최소 비용
dp = [[INF] * n for _ in range(full)]
 
# 출발 도시는 0번 도시
# 0번 도시만 방문한 상태는 mask = 1
dp[__________][__________] = 0
 
# TODO 2. 모든 방문 상태를 순회한다
for mask in range(1, full):
 
    # TODO 3. 현재 마지막 도시 u를 순회한다
    for u in range(n):
 
        # 아직 도달할 수 없는 상태라면 건너뛴다
        if dp[mask][u] == __________:
            continue
 
        # TODO 4. 다음에 방문할 도시 v를 고른다
        for v in range(n):
 
            # 이미 방문한 도시이거나, u -> v 길이 없으면 건너뛴다
            if (mask & (__________)) or w[u][v] == 0:
                continue
 
            # TODO 5. v를 방문한 새로운 상태를 만든다
            nxt = mask | __________
 
            # TODO 6. dp 갱신
            dp[nxt][v] = min(
                dp[nxt][v],
                ________________________________
            )
 
ans = INF
 
# 모든 도시를 방문한 상태
all_visited = full - 1
 
# TODO 7. 마지막 도시 u에서 다시 0번 도시로 돌아오는 비용을 더한다
for u in range(1, n):
    if w[u][0] != 0:
        ans = min(
            ans,
            ________________________________
        )
 
print(ans)

드 부루인 수열

**드 브루인 수열(De Bruijn sequence)**은 문자열의 일종으로, 글자의 종류가 $k$일 때 만들 수 있는 길이가 $n$인 모든 문자열을 정확히 한 번씩 포함하는 것을 말한다. 드 브루인 수열의 길이는 $k^n+n-1$이 된다. 예를 들어 $n=3$이고 $k=2$일 때, 드 브루인 수열의 예는 다음과 같다.

$$0001011100$$

이 문자열의 길이가 3인 부분 문자열은 3bit의 모든 조합인 $000,001,010,011,100,101,110,111$이다.

길이가 $n-1$인 모든 문자열이 노드에 대응되고, 수열에 한 글자를 덧붙이는 것이 간선에 대응되는 그래프를 생각하자.² 드 브루인 수열은 이 그래프의 오일러 경로와 항상 대응된다. 예를 들어 그림 14의 그래프는 $n=3$이고 $k=2$인 경우에 대응된다. 드 브루인 경로를 찾기 위해서는 임의의 노드에서 시작하여 모든 간선을 정확히 한 번 방문하는 오일러 경로를 찾으면 된다. 시작 노드와 간선의 글자를 차례로 더하면 $k^n+n-1$개의 글자로 이루어진 문자열이 되고 이는 올바른 드 브루인 수열이 된다.

• 그림 14. 오일러 경로를 이용하여 드 브루인 수열 찾기
  • 

나이트 투어

**나이트 투어(knight’s tour)**는 $n\times n$ 체스판에서 나이트를 체스의 규칙에 맞게 움직이면서 모든 칸을 정확히 한 번 방문하는 경로이다. 시작했던 칸으로 돌아올 수 있는 경우를 닫힌 나이트 투어라고 하고, 그렇지 않은 경우를 열린 나이트 투어라고 한다. 예를 들어 그림 15에 $5\times 5$ 체스판의 열린 나이트 투어가 나와 있다.

• 그림 15. $5\times 5$ 체스판의 열린 나이트 투어
  • 

체스판의 각 칸이 노드가 되고, 나이트가 체스의 규칙에 따라 두 칸 사이를 이동할 수 있는 경우를 간선으로 연결한 그래프를 생각하자. 나이트 투어는 이 그래프의 해밀턴 경로에 대응된다. 나이트 투어를 찾는 자연스러운 방법은 퇴각 검색을 이용하는 것이다. 규칙에 맞게 움직이는 방법이 매우 많기 때문에, 투어를 빠르게 찾는 방향으로 나이트를 움직이는 휴리스틱(heuristic)을 이용해야 탐색을 효율적으로 수행할 수 있게 된다.

바른스도르프 규칙(Warnsdorf’s rule) 은 나이트 투어를 찾기 위한 간단하고 효율적인 휴리스틱이다. 이 규칙을 이용하면 판의 크기가 크더라도 효율적으로 경로를 찾을 수 있다. 아이디어는 나이트를 움직일 수 있는 여러 칸이 있을 때, 다음으로 움직일 수 있는 경우가 가장 적은 곳으로 움직이는 것이다. 그림 16을 예로 들면, 다음으로 갈 수 있는 칸은 $a\dots e$로 표기된 다섯 칸이다. 이 경우 바른스도르프 규칙에 따르면 $a$ 칸으로 이동해야 하는데, 이 칸에서 다음으로 갈 수 있는 경우의 수가 한 가지뿐이기 때문이다. 다른 칸으로 이동하면 경우의 수가 세 가지가 된다.

• 그림 16. 바른스도르프 규칙을 이용하여 나이트 투어 찾기
  • 

Footnotes

1. 이 조건에는 예외가 있는데, 다음에 나올 두 번째 조건을 만족하는 노드의 진입 차수가 1이고 진출 차수가 0이거나, 진입 차수가 0이고 진출 차수가 1인 경우에는 같은 강결합 컴포넌트에 속하지 않아도 오일러 경로가 존재할 수 있다. ↩

2. 혹은, 문자열의 맨 앞 글자를 제거하고 맨 뒤에 한 글자를 추가하는 것이 간선에 대응된다고 생각할 수도 있다. ↩