재귀(3) - 하노이의 탑

하노이의 탑 문제

하노이의 탑은 n개의 크기가 다른 원반을 가장 큰 순서부터 위로 쌓아올린 상태에서 3개의 기둥에 첫번째 기둥부터 마지막 기둥까지 모든 원반을 옮기는 문제이다. 

조건1) 1번에 1개의 원반만 움직일 수 있다.
조건2) 큰 원반은 작은 원반 위에 쌓을 수 없다.

하노이의 탑은 한번쯤은 접해봤을 문제이다. 이것을 코드로 어떻게 구현을 해야할까 ?

//하노이의 탑 구현코드
    static void move(int no , int x , int y){
        if(no > 1)
            move(no - 1 , x , 6 - x - y);
        System.out.printf("원반[%d]을(를) %c번 기둥에서 %c번 기둥으로 옮김\n",no , 'A'- 1 + x  , 'A' - 1 + y);
        if(no > 1){
            move(no -1 , 6 - x - y, y);
        }
    }
    //메인 함수
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.print("원반의 개수 : ");
        int n = stdIn.nextInt();

        move(n, 1, 3);		// 제1기둥에 쌓인 n 개를 제3기둥으로 이동
    }

위의 코드경우 재귀함수를 사용하여 구현했다. 처음에 필자도 구현한 코드를 보면서 이해하려고 많은 시간이 걸렸던 것같다. 개인적으로 이해한 부분은 하나의 그룹 단위로 묶어보는 것이다. 먼저 기둥이 3개이며 한쪽에는 n개의 원반이 있으니 나머지 기둥은 2개이다. 이것을 이용해서 그룹으로 이동 시키는 것이다. 즉, 3개 이상일시 옮길 떄 모든 기둥이 가득차게된다. 그리고 활용할 수 있는 기둥은 2개이기에 2개 원반을 각각 나누고 다시 합치고 남은 공간은 다음 원반을 옮기고 그룹을 다시 이동시키고 하나로 합치게 하는 것이다.

이를 위와같이 첫번째에서는 펼치고 두 번째 재귀에서는 다시 모으도록 해주면 된다. 

4개의 원반경우

3개의 원반경우

위에 출력 결과를보면 매개변수로 재귀 호출 시 넘겨주는 x , y값이 재귀호출이 반복적으로 일어나면서 어떻게 변화하는지와 원반이 어떤식으로 이동시켜야 하는지 알 수 있다고 본다.

//재귀를 사용하지 않고 구현
static void move(int no , int x, int y){
        int[] xstk = new int[100]; // 원반들의 시작위치
        int[] ystk = new int[100]; // 원반들의 이동시킬 위치
        int[] sstk = new int[100]; // 상태저장
        int ptr = 0; // 배열 포인터 역할 변수
        int sw = 0; // 상태변화를 위한 변수

        while (true){
            if(sw == 0 && no > 1){ // 퍼뜨리기
                xstk[ptr] = x;
                ystk[ptr] = y;
                sstk[ptr] = sw;
                ptr++;
                no = no - 1;
                y = 6 - x - y;
                continue;
            }
            System.out.printf("원반[%d]을(를) %d 기둥에서 %d 기둥으로 이동\n",no , x , y);
            if(sw == 1 && no > 1){ // 다시 그룹으로 모으기
                xstk[ptr] = x;
                ystk[ptr] = y;
                sstk[ptr] = sw;
                ptr++;
                no = no - 1;
                x = 6 - x - y;
                if(++sw == 2) sw = 0;
                continue;
            }
            do{
                if(ptr-- == 0)
                    return;
                x = xstk[ptr];
                y = ystk[ptr];
                sw = sstk[ptr] + 1;
                no++;
            }while (sw == 2);
        }
    }