하노이 탑 문제 해결하기

문제 설명

세개의 탑이 있고 반경이 서로 다른 n개의 원반이 있다. 

1. 한 번에 하나의 원반만 옮길 수 있다.

2. 쌓여있는 원반은 항상 아래의 원반보다 위의 원반이 작아야한다.

3. n개의 원반을 A에서 C로 옮겨라. 

 

원반의 이동 횟수를 최소화하면서  이동 순서를 출력하라

 

문제 접근

위의 조건을 만족하며 n개의 원반을 C로 이동시키기 위해서는 반복적인 동작을 필요로 한다. 원반의 개수가 짝수인 경우 첫번째 원반을 B로 이동시키고, 홀수인 경우 C로 이동시키면서 처리하게 된다.  크게 생각해보면 n번의 원반을 C로 옮기기 위해서는 1부터 n-1번까지의 원반이 B에 위치해 있어야 한다. 즉 이 부분을 재귀적으로 처리한다면 문제를 쉽게 해결할 수 있다.

 

문제 해결

1. n번의 원반을 목적지(C)로 옮기기 위해 n-1까지의 원반을 경유지(B)로 옮긴다.

2. n번째의 원반을 목적지로 옮긴다.

3. 경유지에 있는 n-1까지의 원반을 목적지로 옮긴다. 

 

위의 과정이 반복적으로 처리되므로 이를 재귀함수로 구현하면 된다.

 

그럼 종료 조건은 무엇일까?

 

n개의 원반을 목적지로 이동시킬 때 마지막 1번 원반이 목적지인 C로 이동을 해야 마무리가 된다. 따라서 1번을 움직일 때 함수를 종료시키면 된다.

자바 코드로 구현하면 다음과 같다.

이 재귀식은 함수를 한번 호출하면 2번 재귀 호출되고 마지막 n이 1일 경우 1번 실행되므로  2^n - 1의 시간이 걸린다. 따라서 시간복잡도는O(2^n)이다.

                          // (n번째 원반, 출발지, 경유지, 목적지)
static void hanoi(int n, int start, int via, int to) {
    count++;
    if(n == 1){
        System.out.println(start + " " + to + '\n');  //원반 이동
        return;
    } else {
        hanoi(n-1, start, to, via);
        System.out.println(start + " " + to + '\n'); //원반 이동
        hanoi(n-1, via, start, to);
    }
}

 

원반의 이동횟수

n번의 원반을 C로 옮기기 위해서는 n-1번까지의 원반을 B로 옮기고 n번을 C로, 그리고 n-1번까지의 원반을 C로 옮겨야 한다. 따라서 공식화하면 다음과 같다.

하지만 이동횟수를 구하기 위해서 위 식처럼 계산을 해야할까? 만약 n개의 이동횟수를 구하려면 O(2^n)만큼의 시간이 걸릴 것이다.

위 규칙에서 일반항을 찾으면 2^n - 1 과 같다는 것을 알 수 있다. 따라서 n의 값만 알면 O(1)의 시간복잡도로 이동횟수를 구할 수 있다.

 

 

의문점

Tail Recursion : 재귀 호출이 끝나면 결과 값에 아무 일도 하지 않고 결과만 바로 반환하도록 하는 방법(호출함수와, 호출 당할 함수 필요) → 스택오버플로우를 해결할 수 있다.

 

의문 - Tail Recursion으로 하노이를 구현할 수 있을까?

- 하노이의 경우 결과가 아닌 과정을 구하는 것이다 보니까 Tail Recursion을 쓰기에는 어려움이 있다고 생각한다.