백준 알고리즘 11729번 하노이 탑 이동순서 JAVA

 

 

하노이의 탑은 프랑스 수학자 에두아르 뤼카가 클라우스 교수의 필명으로 1883년 발표한 문제다. 한번에 한개의 원판만 옮길 수 있고, 큰 원판이 작은 원판 위에 있어서는 안된다.

 

하노이의 탑을 해결하는 방법은 재귀호출을 사용하는 것이다. 원판의 개수를 n이라 가정하면 (2n -1)번(메르센 수) 이동으로 원판을 모두 옮길 수 있게 된다. 

 

 

 

백준 알고리즘 11729번 문제는 워낙 유명한 문제라서 알고리즘 강의에 꼭 등장하는 예제다. 핵심은 n개의 원판을 옮기는 문제를 원반 n-1개를 이동하는 문제로 나누는 과정을 재귀함수로 구현하는 것이다.  최종적으로 옮겨야 되는 원판이 1개가 되었을 때 이동해야 할 경로를 출력하고 복귀하게 된다.

 

마지막에 쌓이는 결과물들이 하나씩 쌓이면서 옮겨야 하는 원판의 개수 n은 줄어들게 되고 프로그램은 종료가 된다. 백준 코드에 업로드할 때는 StringBuilder를 사용해야 한다. 원판을 옮길 때 마다 출력을 개별적으로 해주면 (recur 메소드 안에서 System.out.println() 사용)을 해주면 시간초과 에러가 발생한다.

 

 

 

JAVA Code

import java.util.Scanner;

public class A_11792 {
    public static StringBuilder result = new StringBuilder();

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int X = in.nextInt();
        
        
        System.out.println((int)(Math.pow(2, X)-1));
        recur(X, 1, 3, 2);
        System.out.println(result);

    }

    public static void recur(int count, int from, int to, int x){
        if(count <= 1){
            // System.out.println(from+" "+to);
            result.append(from+" "+to+"\n");
            return;
        }
        recur(count-1, from, x, to);
        // System.out.println(from+" "+to);
        result.append(from+" "+to+"\n");
        recur(count-1, x, to, from);
    }
}