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

문제

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

풀이

• 세 개의 장대

• 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다.

• 각 원판은 반경이 큰 순서대로 쌓여있다.

• 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

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

• 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라.

재귀를 이용해 하노이 탑의 이동 알고리즘을 구현하는 문제입니다.

자세한 풀이는 [백준/파이썬] 1914번: 하노이 탑을 참고해 주세요.

코드

import java.io.*;

public class Main_11729 {
	static StringBuilder sb = new StringBuilder();
	
	private static void hanoi(int n, int start, int mid, int end) {
		if (n == 1) {
			sb.append(start).append(' ').append(end).append('\n');
			return;
		}
		hanoi(n-1, start, end, mid);
		sb.append(start).append(' ').append(end).append('\n');
		hanoi(n-1, mid, start, end);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int k = (int) Math.pow(2, n) - 1;
		System.out.println(k);
		
		hanoi(n, 1, 2, 3);
		System.out.println(sb.toString());
	}

}