[BOJ] 11729. 하노이 탑 이동 순서

재귀를 사용하는 대표적인 문제이다.

N개의 원판을 옮기려면 크게 3가지 부분으로 생각하여 접근할 수 있다. 첫번째로 N-1개의 원판을 목적지가 아닌 중간 지점 고리로 옮겨놓고, 두번째로는 가장 밑바닥에 위치한 원판을 목적지로 옮긴다. 마지막으로 중간지점에 위치해있던 N-1개의 원판을 목적지 고리로 옮기는 과정을 반복하다보면 전체 N개의 원판을 목적지로 옮기는 것이 가능하다. 재귀함수의 기저조건으로는 옮길 원판이 없는 경우를 사용하였다.

package chap06;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_11729_재귀 {
    static StringBuilder sb;
    static int total;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int circle = Integer.parseInt(br.readLine());
        sb=new StringBuilder();
        
        total=0;
        hanoi(circle,1,2,3);
        System.out.println(total);
        System.out.println(sb.toString());
        
    }
    static void hanoi(int circle,int start,int temp, int dest) {
        if(circle==0)
            return;
        
        hanoi(circle-1, start, dest, temp);    //n-1개를 중간지점으로 옮기기
        sb.append(start + " "+dest+"\n");
        total++;
        hanoi(circle-1,temp,start,dest);    //중간지점에 있는 n-1개를 최종지점으로 옮기기
    }
    
}