[알고리즘] 백준 11729 자바 JAVA 하노이의 탑

 

 

 

public class BaekJoon_11_11729 {

	public static StringBuffer sb = new StringBuffer();

	public static void hanoi(int n, int start, int remain, int target) throws IOException {
		if (n == 1)
			sb.append(start).append(" ").append(target).append("\n");
		else {
			hanoi(n - 1, start, target, remain); // n-1개의 원판을 남는 타워에 넣는다.
			sb.append(start).append(" ").append(target).append("\n"); // 그리고 남은 원판  1개(가장 큰 원판)를 목적지로 옮긴다.
			hanoi(n - 1, remain, start, target); // 남는 타워에 넣었던 n-1개의 원판을 목적지 타워로 옮긴다.
		}
	}

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

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

		writer.write((int) Math.pow(2, n) - 1 + "\n");
		hanoi(n, 1, 2, 3);
		writer.write(sb.toString());

		writer.flush();
		writer.close();
		reader.close();
	}

}

 

어릴 때 직접 놀이로 해보고 공식정도를 알고 있던 문제이다. 

 

재귀로 푸는 문제인데 hanoi 함수 인자를 보면 n start remain target 이렇게 4가지이다.

 

완전 정복식으로 푸는 재귀문제라 n을 줄여나가다가 더이상 줄일 수 없을 때 거슬러 올라가는 방식으로 진행한다. 그리고 나머지 start는 첫번째, remain은 두번째, target은 세번째 탑(bar)를 의미한다. start에서 target으로 옮겨야되는 함수이다. 먼저 else문의 첫번째 재호출 함수를 보면 tartget의 위치에 remain이 들어가 있다. 이것의 의미는 n-1개의 원반을 남은(remain) 두번째 탑에다가 넣으라는 의미이다. 그리고 두번째 줄은 그리고 남은 원판 1개를 목적지로 옮기라는 의미이고 세번째 재호출은 이제 남은 두번째 탑에 있는 것은 목적지 타워로 옮기라는 뜻이다. 

 

직접 시뮬레이션을 해보면 직접 놀이기구원판을 옮기는 느낌하고는 다르긴하다.. 재귀가 의외로 생각의 전환을 요구한다.