[코딩테스트]백준 #11729

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

코드

import java.util.*;
import java.io.*;

public class Main {

	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void Hanoi(int N, int start, int mid, int to) throws IOException {
		if(N==1) {
			bw.write(start+" "+to+"\n");
			return;
		}
		Hanoi(N-1,start,to,mid);
		bw.write(start+" "+to+"\n");
		Hanoi(N-1,mid,start,to);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		bw.write((int)(Math.pow(2,N)-1)+"\n");
		Hanoi(N,1,2,3);
		bw.flush();
		bw.close();

	}
}

해설

우선 기본적으로 하노의 탑에서 n개의 블록을 다른 곳으로 옮기는 데에 최소 횟수는 2^n-1 회이다. 여기서 또한 블록을 어떻게 옮기는 것까지 표현해주어야 하는데 재귀 함수를 이용하여 이전의 n-1만큼의 블록을 옮긴 뒤에 해당 자리로 n번째의 블록을 옮긴 뒤 다시 n-1만큼의 블록을 옮겨주는 메커니즘이다. 따라서 예시를 3으로 하고 3번째 칸으로 옮긴 다고 하면 2개의 블록을 2로 먼저 옮긴 뒤에 3짜리 블록을 3으로 옮기고 2개의 블록을 3으로 옮겨주면 된다. 따라서 해당 재귀를 사용한다. 추가로 실행되는 횟수가 많기 때문에 System.out.println과 scanner를 쓰지 않고 좀 더 빠르게 처리되는 BufferedReader, BufferedWriter를 사용했다.