[백준] 11729 : 하노이 탑 이동 순서 <JAVA>

 

문제: N개의 원판 개수를 입력 받았을 때, 이동 과정 출력

 

• 하노이 탑의 원리를 알기!
• 하노이 탑 이동 횟수 = 2^N - 1
• 한 번 이동할 때, 제일 위에 있는 원판 하나만 이동 가능
• 크기가 큰 원판은 작은 원판 위에 쌓을 수 없음
• 이동 방법(위치1에 원판 n개가 있다고 가정)
  1. n-1개의 원판을 위치 2로 옮기기
  2. 마지막 원판을 위치 3으로 옮김
  3. n-1개의 원판을 다시 위치 3으로 옮김

 

import java.util.Scanner;
 
public class Main {
 
	public static StringBuilder sb = new StringBuilder();
 
	public static void main(String[] args) throws IOException {
        
	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    sb.append((int)(Math.pow(2,N)) - 1).append('\n');

    hanoi(N,1,2,3);

    System.out.println(sb);
	}
 
	
		// N : 원판의 개수, start : 출발지, mid : 옮기기 위해 이동해야 장소, to : 목적지
   public static void hanoi (int N, int start, int mid, int to){
     if(N == 1){
      sb.append(start + " " + to + "\n");
      return ;
     }

     //1. move N-1 from 'start' to 'mid'
     hanoi(N-1, start, to, mid);

     //2. move last one from 'start' to 'to'
     sb.append(start + " " + to + "\n");

     //3. move N-1 from 'mid' to 'to'
     hanoi(N-1, mid, start, to);
   }
}