[백준] 11729 하노이 탑 이동순서 풀이

알고리즘 중 재귀의 대표적인 문제 하노이의 탑 문제를 풀어보았다.

 

문제 링크 : https://www.acmicpc.net/problem/11729

 

---

 

풀이

import java.util.Scanner;

/**
 * 첫째 줄에 옮긴 횟수 K를 출력한다.
 * 두 번째 줄부터 수행 과정을 출력한다.
 */

public class Main{
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        int result = hanoi(n, 1, 3, 2);
        
        System.out.println(result);
        System.out.println(sb);
    }
    
    public static int hanoi(int n, int from, int to, int temp){
        if(n == 0){
            return 0;
        }
        
        int count = 0;
        
        count += hanoi(n-1, from, temp, to);
        
        sb.append(from + " " + to + "\n");
        
        count++;
        count += hanoi(n-1, temp, to, from);
        
        return count;
    }
}