[Algorithm] Hamiltonian cycle problem - backtracking

해밀토니안...!

해밀토니안 자체는 사람 이름이 아니고, '해밀턴'씨가 만들어서 해밀토니안인데

 

 

이 아저씨도 약간 다작해서 짜증나는 사람이다. 물리학도 수학도 컴퓨터공학도를 동시에 고통주는 이 능력...

 

 

아무튼 해밀토니안 사이클은 다음과 같은 문제이다. 

 

 

모든 정점을 한번씩 방문하고 첫 지점으로 돌아와야 한다! 그런 길이 존재할까???

 

(directed graph도 되고 undirected graph도 됨)

 

 

 

다음과 같이 (못그린) 그래프가 있다고 해 보자. 

 

1부터 시작해서 모든 정점을 다 방문하고 다시 1로 돌아오는 path가 있을까??

 

 

이를 위해서 다음과 같은 표를 하나 그렸다. 

 

일단 첫 시작점은 1이니까

 

 

1을 써준다. 다음으로

 

앞에 나오지 않고, 바로 앞 칸과 이어져 있는 정점을 써준다. 

 

 

 

이렇게! 

 

마지막 칸이 5가 되었다. 그러면 다시 0으로 바꿔준다. 

 

 

 

그 앞칸을 4에서 5로 올려준다. 하지만 바로 앞 칸인 3과 5는 만나지 않으므로 5도 0으로 올려준다. 

 

 

3을 4로 올려준다. 2와 4는 근접하므로 괜찮다. 

 

 

5를 채워줬는데, 3과 5는 인접하지 않으므로 fail...

 

 

이런식으로 쭉쭉 돌면서 tree를 그리게 된다.