백준 1914: 하노이 탑(java/python)

문제

---

풀이

 

하노이 탑 문제는 재귀(recursion)를 이용해 풀 수 있다.

hanoi(N, from, temp, to)

원판의 개수 N과 세 장대 from, temp, to를 변수로 가지는 hanoi() 함수를 사용한다. 이때 hanoi() 함수는 ① N개의 원판을 ② temp 장대를 이용하여 ③ from 장대에서 to 장대로 옮긴다.

 

N개의 원판을 from 장대에서 to 장대로 옮기려면, 우선 from 장대에 걸려 있는 원판들 중 가장 아래에 있는 것(=가장 큰 것)을 제외한 모든 원판을 temp 장대로 옮긴 뒤 남아 있는 원판을 to 장대로 이동시켜야 한다.

hanoi(N-1, from, to, temp)

이후, temp의 원판들을 to 장대로 옮기면 하노이 탑 문제를 해결할 수 있다.

hanoi(N-1, temp, from, to)

위 과정을 정리하면 아래와 같다.

static void hanoi(int n, int from, int temp, int to) {
	if (n == 1) {
		//from에서 to로 이동, 이동 횟수++
		return;	//종료
	}
	else {
		hanoi(n - 1, from, to, temp);	//from의 (n-1)개 원판을 temp로 이동
		//from에 남은 1개 원판을 to로 이동, 이동 횟수++
		hanoi(n-1, temp, from, to);	//temp에 있는 모든 원판을 to로 이동
	}
}

 

작성한 hanoi() 함수를 사용하여 N에 따른 이동 횟수 K를 계산해 보면, K=2^N-1의 관계가 성립함을 알 수 있다.

이를 이용하여 이동 횟수 K를 hanoi() 함수 내에서 계산하지 않고 hanoi()와 별도로 구할 수 있으며, N≤20일 때만 hanoi()를 호출하여 프로그램 효율을 개선할 수 있다.

 

전체 코드

 

1. java

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

public class Main {
	static StringBuilder sb;
	
	static void hanoi(int n, int from, int temp, int to) {
		if (n == 1) {
			sb.append(from+" "+to).append("\n");
			return;
		}
		else {
			hanoi(n - 1, from, to, temp);
			sb.append(from+" "+to).append("\n");
			hanoi(n-1, temp, from, to);
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		sb=new StringBuilder();
		
		int N=scanner.nextInt();
		
		BigInteger K=new BigInteger("2");
		K=K.pow(N).subtract(BigInteger.ONE);
		
		System.out.println(K);
		
		if(N<=20) {
			hanoi(N, 1, 2, 3);
			System.out.println(sb);
		}
	}
}

출력 효율을 위해 StringBuilder()를 사용했다.

 

자바 풀이에서는 이동 횟수를 BigInteger 형으로 선언해야 함에 주의하자. 입력값의 범위가 1≤N≤100이므로, long형을 사용해도 N=63까지밖에 계산할 수 없다(N=63일 때 K=9223372036854775807이고 이는 long형 최댓값).

 

2. python

N=int(input())

print(2**N-1)   #K

def hanoi(N, frm, temp, to):
    if N == 1:
        print(frm, to)
        return
    else:
        hanoi(N-1, frm, to, temp)
        print(frm, to)
        hanoi(N-1, temp, frm, to)

if N <= 20:
    hanoi(N, 1, 2, 3)