[자바] 재귀함수 - 하노이 탑 이해하기

하노이 탑은 3개의 막대가 있고 원반을 목표 막대로 옮기는 과정이다. 

이 과정에서

1. 한번에 한개의 원반만 움직일 수 있다.

2. 가장 위에 있는 원반만 움직일 수 있다.

3. 큰 원반이 작은 원반 위에 있을 수 없다.

위와 같이 3개의 규칙을 지켜야한다.

 

원반의 개수를 n이라고 한다면

n = 1일때

A->C

총 1번이 걸린다.

n = 1일 때

 

n = 2일때

A->B

A->C

B->C

총 3번이 걸린다.

n = 2일 때

 

n=3일 때

A->B(가장 큰 원반 한개만 남겨놓고 나머지 다 B로 이동)

- A->C

- A->B

- C->B

A->C(가장 큰 원반 한개 A에서 C로 이동)

B->C(B에 남아있는 원반들 C로 이동. )

- B->A

- B->C

- A->C

총 7번이 걸린다.

n=3일 때

 

일반식을 유도해보면

f(n) = 1+2f(n-1)이라는 것을 알 수 있다.

왜냐하면 가장 큰 원반을 제외하고 임시 기둥으로 옮기는 과정이 f(n-1)번 걸리고 목표 기둥으로 가장 큰 원반 옮기는데 1번, 임시 기둥에서 목표기둥으로 옮기는 과정 f(n-1)번 걸리므로 총 1+2f(n-1)번 걸리게 된다.

위와 같은 식을 이용하여 n개의 원반을 입력받고 원반이 이동하는 과정을 보여주며 총 이동 횟수를 출력해주는 코드를 작성하였다.

 

import java.util.Scanner;

public class main{
	static int count = 0;
	static void hanoi(int n, char from, char temp, char to){
		if(n==1){
            System.out.printf("%c -> %c\n", from, to);
            count++;
            return;
        }
        hanoi(n-1,from,to,temp);
        System.out.printf("%c -> %c\n", from,to);
        count++;
        hanoi(n-1, temp, from, to);
    }
	
    public static void main(String[] args) {
        
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	hanoi(n, 'A', 'B', 'C');
    	System.out.println(count);        
    }
}

 

n=3을 입력하여 실행한 결과

 

출처 : 혀니C코딩, https://www.youtube.com/watch?v=vq7dpFWpwAE&t=102s