[백준] 11729번 : 하노이 탑 이동 순서

문제

 

유명한 하노이 탑 문제로 1번 탑에서 3번 탑까지 원판의 순서를 유지하면서

옮기기 위한 과정과 이동 횟수를 출력하는 문제다.

 

접근 방식

재귀를 사용해서 풀 수 있는 교과서 같은 문제로

하노이 탑에 대해서는 잘 알고 있지만 코드로 짜는건 많이 어려웠다.

(재귀가 참 이론은 쉬운데 귀납적으로 생각하고 구현하는 것이 어려운거 같다...)

 

위에서부터 1번 원판, 2번 원판, ... , n번 원판이라고 했을 때

맨 밑에 있는 n번째 원판을 제외한 모든 원판을 2번 탑으로 옮길 수 있다면

n번 원판을 3번 탑으로 옮길 수 있다는 것이 성립된다.

 

그 후에 2번째 탑에 있는 원판들을 모두

3번 탑으로 그대로 옮길 수 있다면 하노이 탑의 원리대로

1번 탑의 원판들을 그대로 3번 탑으로 옮길 수 있는 것이다.

 

그러면 방금 정리한 내용들이 정당한지 확인하면 되는데

n - 1개 일 때는 당연히 원판이 총 두 개니

n - 1번 원판을 2번 탑으로 옮기면 n번 원판을 3번 탑으로 옮길 수 있고

다시 n - 1번 원판을 3번 탑으로 옮기면 그대로 옮길 수 있다는 것을 알 수 있고

이를 이제 코드로 구현하면 된다.

 

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());

		bw.write(((int) Math.pow(2, n) - 1) + "\n");

		hanoi(1, 3, n);

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private static void hanoi(int start, int target, int n) {
		if (n == 1) {
			sb.append(start).append(" ").append(target).append("\n");
			return;
		}

		hanoi(start, 6 - start - target, n - 1);

		sb.append(start).append(" ").append(target).append("\n");

		hanoi(6 - start - target, target, n - 1);
}