하노이의 탑

algorithm-tower-of-hanoi.md

하노이의 탑

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

풀이

기둥이 A, B, C 있고 A 기둥에 원판이 n개 쌓여있을 때,

A -> (C를 거쳐) B로 옮기는 경우의 수 : a_n-1

A -> C로 옮기는 경우의 수 : 1

B -> (A를 거쳐) C로 옮기는 경우의 수 : a_n-1

따라서,

a_n = a_n-1 + 1 + a_n-1

양변에 1을 더하면,

(a_n + 1) = 2(a_n-1 + 1)

이것은 첫째항이 a_n + 1 이고, 공비가 2인 등비수열이다.

기본 등비수열 점화식이 (a_n + p) = (a₁ + p) * k^n-1 이므로

a_n = 2 * k^n-1 - 1

a₀ = 1 이므로,

a₀ = 2 * k^-1 - 1 = 1

k^-1 = 1

따라서,

k = 1

최종적으로,

a_n = 2^n-1 - 1

Code Type A

	static String[] top = new String[]{"SIZE-1", "SIZE-2", "SIZE-3"};
	static Stack<String> A = new Stack<>();
	static Stack<String> B = new Stack<>();
	static Stack<String> C = new Stack<>();
	static int moveCount = 0;

	public static void main (String[] args) {
		A.push(top[2]);
		A.push(top[1]);
		A.push(top[0]);
		hanoi(A.size(), "A", "B", "C");
		System.out.println(moveCount + " moves.");
	}

	public static void hanoi (int topNo, String from, String via, String to) {
		if (topNo == 1) {
			move(from, topNo, to);
			return;
		}
		// A -> C -> B
		hanoi(topNo - 1, from, to, via);
		// A -> C
		move(from, topNo, to);
		// B -> A -> C
		hanoi(topNo - 1, via, from, to);
	}

	public static void move (String from, int topNo, String to) {
		Stack<String> fromStack = getStack(from);
		Stack<String> toStack = getStack(to);
		toStack.push(fromStack.pop());
		System.out.printf("%s--(%s)-->%s\n", from, top[topNo - 1], to);
		System.out.println("A Stack" + A);
		System.out.println("B Stack" + B);
		System.out.println("C Stack" + C);
		System.out.println("--------------");
		moveCount += 1;
	}

	public static Stack<String> getStack(String stackName) {
		if ("A".equals(stackName)) {
			return A;
		} else if ("B".equals(stackName)) {
			return B;
		} else {
			return C;
		}
	}

Code Type B

	static int count = 0;
	
	public static void main(String[] args) {
		Stick A = new Stick("A");
		Stick B = new Stick("B");
		Stick C = new Stick("C");
		
		A.disks.push(Disk.DISK_C);
		A.disks.push(Disk.DISK_B);
		A.disks.push(Disk.DISK_A);
		
		hanoi(A.disks.size(), A, B, C, () -> {
			System.out.println("Stick A:" + A.disks);
			System.out.println("Stick B:" + B.disks);
			System.out.println("Stick C:" + C.disks);
		});
		System.out.println(count + " moves.");
	}
	
	public static void hanoi(int diskNo, Stick from, Stick via, Stick to, Runnable showStatus) {
		if (diskNo == 1) {
			Stick.move(from, to);
			showStatus.run();
			count += 1;
			return;
		}
		// A -> C -> B
		hanoi(diskNo - 1, from, to, via, showStatus);
		// A -> C
		Stick.move(from, to);
		showStatus.run();
		count += 1;
		// B -> A -> C
		hanoi(diskNo - 1, via, from, to, showStatus);
	}
	
	public enum Disk {
		DISK_A, DISK_B, DISK_C;
	}

	public static class Stick {
		final String name;
		Stack<Disk> disks = new Stack<>();
		
		public Stick(String name) {
			this.name = name;
		}
		
		static void move(Stick from, Stick to) {
			Disk disk = from.disks.pop();
			to.disks.push(disk);
			System.out.printf("%s--(%s)-->%s\n", from.name, disk, to.name);
		}
		
		@Override
		public String toString() {
			return "Stick[" + name + "]" + disks;
		}
	}

Result

A--(SIZE-1)-->C
A Stack[SIZE-3, SIZE-2]
B Stack[]
C Stack[SIZE-1]
--------------
A--(SIZE-2)-->B
A Stack[SIZE-3]
B Stack[SIZE-2]
C Stack[SIZE-1]
--------------
C--(SIZE-1)-->B
A Stack[SIZE-3]
B Stack[SIZE-2, SIZE-1]
C Stack[]
--------------
A--(SIZE-3)-->C
A Stack[]
B Stack[SIZE-2, SIZE-1]
C Stack[SIZE-3]
--------------
B--(SIZE-1)-->A
A Stack[SIZE-1]
B Stack[SIZE-2]
C Stack[SIZE-3]
--------------
B--(SIZE-2)-->C
A Stack[SIZE-1]
B Stack[]
C Stack[SIZE-3, SIZE-2]
--------------
A--(SIZE-1)-->C
A Stack[]
B Stack[]
C Stack[SIZE-3, SIZE-2, SIZE-1]
--------------
7 moves.