자바 재귀함수 하노이탑 풀이

하노이탑은 작은 원반 위에 큰원반이 위치할 수 있도록 원반을 다른 기둥으로 옮기는 문제입니다.

핵심 규칙은 큰 원반 아래에 작은 원반이 올 수 없다는 것이지요.

이것을 재귀를 통해 풀어보도록 하겠습니다.

3개의 원반이 있다고 할 때 먼저 가장 먼저 해야할 것은 두개의 원반을 옮기기로 한 기둥과 다른 기둥으로 옮기는 것입니다.

 

예를 들어,

3개의 원반을 1기둥에서 3기둥으로 옮긴다고 할 때 

2개의 원반을 1기둥에서 2기둥으로 옮겨야 합니다.

원반 3을 기둥 3으로 옮긴 후 

2개의 원반을 2기둥에서 3기둥으로 옮겨야 합니다.

두개로 갈라집니다.

2개의 원반을 1->2기둥으로 옮기고

원반 3을 기둥 1->3으로 옮기고

2개의 원반을 2->3으로 옮깁니다.

즉 두개의 재귀가 필요합니다.

2개의 원반을 옮기는 과정또한 마찬가지입니다.

원반 1을 기둥 3으로 옮기고

원반 2를 기둥 2로 옮기고

원반 1을 다시 기둥 2로 옮겨야 합니다.

두개의 재귀가 필요합니다.

함수로 표현하면 아래와 같습니다.

static void move(int n, int a, int b) {
	if(n>1) {
		move(n-1,a,6-a-b);
	}
	System.out.println(n+"을"+a+"기둥에서"+b+"기둥으로 이동");
	if(n>1) {
		move(n-1,6-a-b,b);
	}
}
public static void main(String[] args) {
	move(3,1,3);
}

1을1기둥에서3기둥으로 이동
2을1기둥에서2기둥으로 이동
1을3기둥에서2기둥으로 이동
3을1기둥에서3기둥으로 이동
1을2기둥에서1기둥으로 이동
2을2기둥에서3기둥으로 이동
1을1기둥에서3기둥으로 이동