하노이탑(백준 1914)

(출처) https://www.acmicpc.net/problem/1914

📖 개요

유명한 하노이 탑 퍼즐을 구현하는 문제.

원판의 개수가 인풋으로 주어질 때 원판들을 이동시키는 순서를 출력해야 하는 문제였다.

재귀로 접근해야 한다는 것을 알고서 풀었는데도 마땅한 방법을 생각해 내지 못했고 결국 다른 분들의 코드를 참고하고 나서야 이해할 수 있었다.😵

풀이법

만약 위 그림과 같이 5개의 원판을 하노이탑 퍼즐 규칙에 따라 이동시켜야 할 때, 하노이탑 원판의 이동은 크게 3가지로 나눠서 구분 지을 수 있다.

가장 밑에 있는 원판을 기준으로,
첫 번째로 자신 위에 있는 모든 원판을 최종 목적지가 아닌 다른 곳으로 옮겨놓는 작업,
두 번째로 자신이 최종 목적지로 이동하는 작업,
마지막으로 다른 곳에 옮겨놓은 원판들을 다시 자신의 위로 옮겨 놓는 작업이다.

원판의 움직임은 어떤 상황에서든(이동시킬 원판의 개수가 1개밖에 없는 경우 제외. 이 경우는 기저사례로 따로 처리) 예외 없이 전부 이 3가지 과정으로 세분화시킬 수 있고, 가장 밑에 위치한 원판에 대한 움직임을 처리해 주면서 항상 더 작은 부분 문제로 쪼개지는 형태이므로 이 문제는 재귀적으로 해결할 수 있다.

결국 핵심은 이동시켜야 할 원판에서 가장 밑에 있는 마지막 원판의 이동과정은 항상 명확하므로(시작지점에서 도착지점) 마지막 원판의 이동만 확실히 해결하고, 남은 원판들은 부분 문제로 쪼개서 다시 해결하는 것.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	private static StringBuilder sb = new StringBuilder();
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	//private static int cnt = 0; (시간초과..)
	
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		//bw.write(Integer.toString(cnt) + "\n");
		BigInteger cnt = new BigInteger("2");
		cnt = cnt.pow(N);
		cnt = cnt.subtract(new BigInteger("1"));
		bw.write(cnt.toString() + "\n");
		if(N <= 20) {
			recurse(N,1,3);
			bw.write(sb.toString());
		}
		bw.flush();
		bw.close();
	}
	
	public static void recurse(int block, int from, int to) {
		if(block == 1) {
			//cnt++;
			sb.append(from + " " + to + "\n");
			return;
		}
		
		int middle = 6 - from - to;
		
		recurse(block - 1, from, middle); 
		recurse(1,from,to);
		recurse(block-1,middle,to);
	}
}