11729. 하노이 탑 이동 순서 (자바, Java)

 감회가 새로웠다. 고등학교때 지수함수 파트 끝부분에 간략히 언급되었던 하노이의 탑이었다. 여기서 다시 만나다니...

처음에는 감도 안 잡혀서 포기했다가, 별찍기로 재귀함수를 다시 익히게 된 후 다시 풀어서 맞았다.

 

 원리는 생각보다 단순하다. 총 옮긴 횟수 K는 n=1일때 1, n=2일때 3, n=3일때 7...해서 2^n-1이 된다.

직관적으로 와닿지 않는다면, 계차수열로 풀어보면 된다.

n에 따른 K값을 나타내는 수열 n번째 항 = 초항 + 계차수열의 n-1번째항까지의 합이다.

계차수열은 초항이 1이고 공비가 2인 등비수열이므로 계차수열 bn=2^(n-1)이 되고, 등비수열 합공식을 이용하면 된다.

나중에 수학공식 태그를 추가한뒤에 해야겠다..일단 본문보다 길어져서 생략.

 

 아무튼간에 결론만 말하면, n-1개의 원판을 중간지점(초기값은 2번 원판) 으로 옮기고, 마지막 원판을 도착지점(3번 원판)으로 옮기고, 2번 원판에 있는 n-1개의 원판을 도착지점인 3번원판까지 옮기면 된다.

 

 글로 옮기니까 되게 복잡한데, 나중에 그림자료를 추가하도록 하겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int hanoi[][];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 장대에 쌓인 원판의 갯수 
		int k = (int) (Math.pow(2, n)-1); // 옮긴 횟수
		int m = (k-1)/2; // 총 횟수의 가운데 부분.
		hanoi = new int[k][2]; // 하노이의 탑을 옮긴 기록을 순서대로 배열한 것.
		top(m, n, 1, 3); 
		System.out.println(k);
		
		StringBuilder sb = new StringBuilder();
		
		for (int i=0; i<k; i++) {
			sb.append(hanoi[i][0] + " " + hanoi[i][1] + "\n");
		}
		
		System.out.println(sb);

	}
	
	static void top(int m, int n, int start, int end) {
		
		// 하노이의 탑 구하는 매소드
		
		if (n==1) {
			hanoi[m][0] = start;
			hanoi[m][1] = end;
			return; // n=1인 경우, 시작부터 끝까지 옮기는 과정을 그대로 기록한다.
		} else {
			
			int x = (int)(Math.pow(2, n-2));
			int other = 0; // 시작지점과 목표지점을 제외한 중간지점
			
			
			if ((start == 1 || start == 2) && (end == 2 || end == 1)) {
				other = 3;
			} else if ((start == 1 || start == 3) && (end == 3 || end == 1)) {
				other = 2;
			} else if ((start == 2 || start == 3) && (end == 2 || end == 3)) {
				other = 1;
			}
	
			top(m-x,n-1,start,other); // n-1개의 원판을 중간지점까지 재귀호출하여 옮겨주고,
			top(m,1,start,end); // 마지막 n번째 원판은 그대로 옮겨주며, 횟수의 정가운데가 된다.
			top(m+x,n-1,other,end); // 아까 옮겼던 n-1개의 원판을 마저 옮겨주면 끝.
			
			return;
		}		
	}
}