[알고리즘] 하노이 탑

[풀이 방식 - 재귀함수]

하노이탑은 3가지 기둥이 있고 그 중 첫번째기둥에 있는 원판들을 모두 세번째목적 기둥에 옮기는 과정이다.

그 과정에서 자기보다 큰원판은 자기 위로 올라올 수 없다.

 

예를들어 원판이 3개인 경우를 살펴보자

기본 상태

1번째 이동

2번째 이동

3번째 이동

4번째 이동

5번째 이동

6번째 이동

7번째 이동 - 완료

여기서 3번째 이동을 보면 가장 큰 원판을 제외한 모든 원판을 2번기둥에 이동시킨걸 볼 수 있다.

즉 N개의 원판을 3번 기둥에 옮기려면 N-1개의 원판을 2번기둥으로 옮겨야한다.

(N개의원판을 2번기둥으로 옮기려면 N-1개의 원판을 3번기둥에 옮겨야한다.)

 

이 과정을 재귀로 풀어보면

N=3이고 3번기둥으로 모두 옮기고 싶다.

3개의 원판을 3번기둥에 옮기는 데에 필요한 과정은 2개의 원판을 2번기둥에 옮겨야한다.

2개의 원판을 2번기둥에 옮기는 데에 필요한 과정은 1개의 원판을 3번기둥에 옮겨야한다.

1개의 원판을 3번기둥에 옮기는 데에 필요한 과정은 그냥 옮기면 된다.

 

이제 코딩으로 풀이해보자.

public class Main {
    static int cnt;
    public static void main(String[] args) {
        int N = 3;
        cnt = 0;
        hanoi(N, 1, 2, 3);
        System.out.println(cnt);
    }

    // hanoi(n번째로 큰 원반 , 출발위치, 중간위치 , 목적위치)
    static void hanoi(int n, int start, int via, int destination) {
        // 원반이 한개인 경우 시작위치(1번기둥)에서 목적위치(3번기둥)까지옮긴다
        if (n == 1) {
            System.out.println(start + " " + destination);
            //옮긴 횟수 세기
            cnt++;
            return;
        }
        // 그 외의 경우 원반n-1개를 시작위치(1번기둥)에서 중간위치(2번기둥)으로 이동
        hanoi(n - 1, start, destination, via);
        
        // 가장 큰원반을 시작기둥에서 도착기둥으로 이동
        System.out.println(start + " " + destination);
        //옮긴 횟수 세기
        cnt++;
        
        // 중간위치(2번기둥)에 있는 원판들을 목적위치(3번기둥)로 이동
        hanoi(n - 1, via, start, destination);
        return;
    }
}



////출력값////
1 3
1 2
3 2
1 3
2 1
2 3
1 3
7
//////////////

그리고 이 과정에서 재밌는 점을 발견했는데 

원판 개수가

2개일 때 총 움직인 횟수는 3

3개일 때 7회

4개일 떄 15회

5개일 때 31회...

여기서 규칙을 찾았다 N개의 원판을 움직인 총 횟수는 2의 N제곱 -1 번이라는 것이다.

public class Main {
    public static void main(String[] args) {
        int N = 4; //원판개수
        int cnt = (int)Math.pow(2,N)-1;
        System.out.println(cnt);
    }
}

//출력값 : 15//