자료구조&기본 알고리즘 입문(자바)- 하노이의 탑

● 하노이의 탑
하노이의 탑(Towers of Hanoir)은 작은 원반이 위에, 큰 원반이 아래에 취치할 수 있도록 원반을 
3개의 기둥 사이에서 옮기는 문제. 모든 원반은 크기가 다르고 처음에는 모든 원반이 규칙에 맞게 
첫번쨰 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번쨰 기둥으로 최소의 횟수로 옮기면 된다. 
원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 는 없다. 

이미지 출처: https://medium.com/@jamalmaria111/tower-of-hanoi-js-algorithm-3f667fa46f0f

import java.util.Scanner;
// 하노이의 탑

class Hanoi {
	// no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
	static void move(int no, int x, int y) {
		if (no > 1)
			move(no - 1, x, 6 - x - y);

		System.out.println("원반[" + no + "]을 " + x + "기둥에서 " + 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번 기둥으로 옮김
	}
}

해당 move 메서드의 매개변수 no는 옮겨야 할 원반의 개수, x는 시작 기둥의 번호, y는 목표 기둥의 번호. 
기둥 번호를 1,2,3으노 나타내고, 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6 - x- y로 구할 수 있다. 원반은 no개 이므로 다음과 같은 과정을 거치고, 1번, 3번 과정은 재귀 호출에 의해 해결한다. 

1. 바닥 원반을 제외한 그룹(원반[1] ~원반[no-1]을 시작 기둥에서 중간 기둥으로 옮김
2. 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력 
3. 바닥 원반을 제외한 그룹(원반[1]~원반[no-1)을 중간 기둥에서 목표 기둥으로 옮긴다. 

 

-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893