[백준,BOJ 11729] 하노이 탑 이동 순서(JAVA 구현)

-내 생각

  하노이 탑의 경우 개념은 알겠는데, 재귀 호출의 늪에 빠져버려서 도저히 머릿속으로 상상이 어렵다.. 그래서 그냥 공식처럼 외우기로 했다..

 

-해법

  하노이 탑을 해결하기 위해서 1번 타워에서 3번 타워로 옮기는 것이 기본으로 수행 알고리즘은, n-1개의 원판을 1->3->2 순으로 타워 롤 옮기고, 2->1->3 순으로 3번에 다시 쌓으면 된다고 한다. 그렇기 때문에 재귀 호출을 통해 인자만 변경하면서 전달해주면 된다.

 

import java.util.*;

public class Main {
	static int n,cnt=0;
	static StringBuilder sb = new StringBuilder();
	static void hanoi(int n,int from,int by,int to) {
		cnt++;
		if(n==1) { // 원판이 1개일 때
			sb.append(from+" "+to+"\n");
			return;
		}else { // 원판이 1개가 아닐 때
			hanoi(n-1,from,to,by); // n-1을 한 후, 1->3->2로 원판을 전달
			sb.append(from+" "+to+"\n");
			hanoi(n-1,by,from,to); // n-1을 한 후, 2->1->3으로 원판을 전달
		}
	}
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		hanoi(n,1,2,3);
		System.out.println(cnt);
		System.out.println(sb);
		
	}
	
}