[BAEKJOON] 1914번 하노이탑

※ 3개의 원판을 A(초기)에서 C(목적) 기둥으로 옮기는 과정

 

※ N개의 원판을 A(초기)에서 C(목적) 기둥으로 옮기는 과정

가장 큰 원판 위에 쌓여있는 N-1개의 원판들을 하나의 덩어리로 가정하고 생각해보자.

먼저 덩어리 N-1개의 원판을 B(임시)기둥으로 옮겨놓은 상태에서 가장 큰 원판을 C(목적)기둥으로 이동시키자.

이후, B(임시) 기둥에 있는 N-1개의 덩어리들을 C(목적) 기둥으로 옮기기만 하면 끝이다.

 

더 세세하게 과정을 나누어서  바로 위의 세 번째 그림을 보자.

위와 같이 가장 큰 원판(빨강색)을 C(목적) 기둥으로 옮겼다면 현실적으로 덩어리를 한 번에 C(목적) 기둥으로 옮길 수는 없다. 따라서 그 다음으로 큰 원판(주황색) 역시 C(목적) 기둥으로 옮기는 과정이 필수이다.

그 전에 덩어리에 있는 주황색 위의 N-2개의 원판들을 현재 비어있는 기둥인 A(초기) 기둥으로 옮겨야 한다. 그 이후에야 주황색 원판을 B(임시)에서 가장 큰 원판(빨강색)이 있는 C(목적) 기둥으로 옮길 수 있다.

 

1. 덩어리들을 C(목적) 기둥 이외의 비어 있는 기둥으로 보낸다.

2. 다 드러냈으니 가장 큰 원판은 C(목적) 기둥으로 옮긴다.

3. 위에서 드러냈던 덩어리들을 C(목적) 기둥으로 옮긴다.

 

첫 번째 과정에서 기둥의 위치만 바뀌었을 뿐, 원판들을 덩어리로 생각했을 때 덩어리의 가장 큰 원판을 C(목적) 기둥으로 옮기는 행위는 여전히 동일하다.

 

결과적으로,

차례대로 가장 큰 원판을 C(목적) 기둥으로 옮겼다면 나머지 N-1개, N-2개, .. 의 원판 덩어리들을 옮기는 과정은 반복적인 동일한 행위이기 때문에 재귀호출 방식으로 구현할 수 있다.

 

하지만 여기서 중요한 점이 있다.

덩어리 입장에서 출발, 임시, 목적 기둥의 위치가 계속해서 변할 것이다.

왜냐하면 위의 N-1개의 덩어리를 드러내어 C(목적) 기둥으로 옮기는 것이 아니라 비어 있는 A(출발)기둥이나 B(임시)기둥을 목적 기둥으로, 최종 목표인 C(목적) 기둥을 오히려 임시 기둥으로 가정하고 옮겨야 하기 때문에 덩어리 입장에서는 C가 무조건 목적 기둥이 되지 않는다는 것이다.

 

가장 기본적인 방식으로 아래 코드를 보며 알아보자.

초기 기둥에 있는 덩어리들을 임시 기둥으로 옮겨놓고, 가장 큰 원판을 목적 기둥으로 옮기고, 다시 덩어리들을 목적 기둥으로 옮긴다.

public class HanoiTest {
	public static void main(String[] args) {
		hanoi(3,1,2,3);
	}
	
	public static void hanoi(int n, int from, int temp, int to) {
		if(n==0) return;
		// n-1개(덩어리) 원판 이동
		hanoi(n-1, from, to, temp);
		// n번 원판 이동
		System.out.println(n+" : "+from +" -> "+to);
		// n-1개(덩어리) 원판 이동
		hanoi(n-1, temp, from, to);
	}
}
>> 출력결과
1 : 1 -> 3
2 : 1 -> 2
1 : 3 -> 2
3 : 1 -> 3
1 : 2 -> 1
2 : 2 -> 3
1 : 1 -> 3

---

이제 문제에 적용해보자.

---

20이하의 수를 입력 받으면 하노이탑의 이동 과정을 출력하지 않아도 된다.

쉽게 접근할 수 있던 문제였지만 고려해야할 점이 있었다.

int형 범위를 넘어서면 값이 출력되지 않는다는 것!

BigInteger 클래스를 활용해야 한다.

2022.03.24 - [JAVA] - [JAVA] BigInteger 클래스

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static int cnt, N;
	static StringBuilder sb;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		sb = new StringBuilder();
		N = sc.nextInt();
		BigInteger res = new BigInteger("1");
		if(N<=20) {
			sb.append((int)(Math.pow(2, N) - 1)).append("\n");
			hanoi(N,1,2,3);
		}
		else {
			for(int i=0; i<N; ++i) {
                res = res.multiply(new BigInteger("2")); // 2의 N 제곱
            }
            res = res.subtract(new BigInteger("1")); // 빼기 1
            sb.append(res).append("\n");
		}
		System.out.println(sb.toString());
	}
	
	public static void hanoi(int n, int from, int temp, int to) {
		if(n==0) return;
		hanoi(n-1, from, to, temp);
		sb.append(from+" "+to+"\n");
		hanoi(n-1, temp, from, to);
	}
}

 

[출처]

https://www.acmicpc.net/problem/1914

1914번: 하노이 탑