[BAE/<JOON> 문제풀이] 12287. 해밀턴 경로

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

12287번: 해밀턴 경로

서론

발상 못 떠올려서 검색해보다가 이 문제에 대한 논문이 있다는걸 알았다. ㄷㄷ..

나름 유명한 문제인 것 같다.

https://imada.sdu.dk/u/jbj/DM19/turnering.pdf

---

풀이

발상 실패 후 BF부터 시도해봤다. 당연히 2^n 보다 빠른 알고리즘을 작성할 수 없다. n=100이다.

아래는 검색한 내용을 바탕으로 작성한 풀이다.

 

이 문제의 핵심은 주어지는 그래프가 토너먼트 그래프라는 점이다.

토너먼트 그래프는 모든 정점들이 다른 모든 정점들과 방향 간선으로 이어진 그래프를 지칭하는 용어이다.

즉, 간선의 방향성을 무시하면 완전 그래프이다.

 토너먼트 그래프는 반드시 해밀턴 경로가 있다. 이에 대한 증명은 아래와 같다.

 

정점 수 1인 토너먼트 그래프에서 자명하게 해밀턴 경로가 존재한다. ( 정점 한개만 방문하는 경로 )

이후 정점 수 2개 이상의 토너먼트 그래프에 대해 다음이 성립한다.

새로운 노드 n1을 추가하면 n1 => (1~n1-1) 경로가 신규로 추가된다. 1~n1-1까지의 그래프는 토너먼트 그래프이므로 해밀턴 경로가 있다. 1~n1-1 정점 집합(이하 T1)이 x1 ~ xn1-1을 해밀턴 경로로 가진다고 하자.

n1을 추가한 그래프(이하 T2)가 해밀턴 경로를 가진다면 T1 사이에 n1을 끼워넣을 수 있어야 한다.

다시 말해, T1 을 x1~xk, xk+1~xn1-1 로 양분했을 때 xk => n1 이며 n1 => xk+1 인 k가 최소 하나는 있어야 한다.

k가 1이나 n1-1일 수도 있다 ( n1 -> (x1~xn1-1) 구조 혹은 (x1~n1-1) -> n1 구조 ). 간선은 indegree / outdegree 2가지이므로 조건을 만족하는 k가 하나도 없기 위해서는 아래 3가지 조건을 모두 만족해야한다.

1. n1 => x1 간선 (indegree) 없음

2. xn1-1 => n1 간선 (outdegree) 없음

3. 모든 xp, xp+1 에 대해 outdegree, indegree 구조가 없음

1, 2, 3번 조건을 조합해서 서술하면 x1은 반드시 outdegree여야하고 xn1-1은 반드시 indegree여야 한다.

그런데 이 조건을 만족하면서 3번 조건: outdegree, indegree가 하나도 없는 것은 불가능하다.

따라서 세 조건이 동시에 만족되는 것은 불가능하며 정점 n개의 토너먼트 그래프에 해밀턴 경로가 존재한다면 반드시 정점 n+1개의 토너먼트 그래프에도 해밀턴 경로가 존재한다. 그런데 정점이 1개인 토너먼트 그래프에는 반드시 해밀턴 경로가 존재하므로 모든 토너먼트 그래프에는 해밀턴 경로가 반드시 존재한다.

 

위 증명 과정을 그대로 코드로 옮기면 알고리즘이다. 

T1 을 x1~xk, xk+1~xn1-1 로 양분했을 때 xk => n1 이며 n1 => xk+1 인 k를 찾고 n1을 경로 안에 삽입하는 과정을 여러번 반복하면 된다.

 

어느 정도 배경 지식이 필요한 문제였고, 순수 직관으로 이걸 푼 사람이 있다면 진짜 천재인듯 ㅇㅇ;;

나도 노트에 그래프 몇개 그려보면서 "뭐지? 불가능한 경우는 없는 거 같은데" 까지는 갔지만 증명할 생각을 못하고 다른 풀이 찾아 해맸다 (SCC 문젠줄 알았음..). 코드는 쉽지만 발상이 어려운 문제 같다.

---

코드

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
using ll = unsigned long long;
/*
모든 정점이 연결된 방향 그래프에서 ( 그래프 방향을 무시하면 완전 그래프 = 토너먼트 그래프라고 한다. )
다음 명제가 반드시 참임을 증명
1. 모든 간선이 들어오는 간선이거나 나가는 간선인 정점이 최소 1개 존재하거나
2. 모든 정점을 방문하고 출발 정점으로 돌아오는 길이 V(정점 수)의 경로가 최소 1개 존재한다.
*/
/*
토너먼트 그래프에서는 반드시 해밀턴 경로가 존재한다. 귀납 증명 했던 것 같음. 정점 1개씩 추가해가는 식으로
*/
struct node {
    int n, cnt = 0;   
};
int n;
vector<vector<int>> arr;
// 임의의 노드 3개 k1, k2, k3 를 골라 k1 -> k2 -> k3 가 가능하면 경로 있음.
vector<int> gethp(int idx) {
    if (idx <= 2) {
        if (arr[1][2] == 1) {
            return { 1, 2 };
        }
        else {
            return { 2, 1 };
        }
    }
    auto ret = gethp(idx - 1);
    int vp = -1;
    for (int i = 0; i < idx - 2; i++) {
        if (arr[ret[i]][idx] == 1 && arr[idx][ret[i + 1]] == 1) {
            vp = i + 1;
            break;
        }
    }
    if (vp == -1) {
        if (arr[idx][ret[0]] == 1) {
            ret.insert(ret.begin(), 1, idx);
        }
        else if (arr[ret[idx - 2]][idx] == 1) {            
            ret.push_back(idx);
        }        
    }
    else {
        ret.insert(ret.begin() + vp, 1, idx);
    }    
    return ret;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n; arr = vector<vector<int>>(n + 1, vector<int>(n + 1));     
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 1; j <= i; j++) {
            if (s[j - 1] == '+') {
                arr[i][j] = 1;
            }
            if (s[j - 1] == '-') {
                arr[j][i] = 1;
            }
        }
    }
    /*for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }*/
    auto ret = gethp(n);
    for (int i = 0; i < n; i++) {
        cout << ret[i] - 1 << " ";
    }    
    return 0;
}