[백준/BOJ 11729] 하노이 탑 이동 순서 (Java)

문제 분석

1. 세 개의 장대가 있다
2. 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다.
3. 각 원판은 반경이 큰 순서대로 쌓여있다.
4. 제약 조건에 따라 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다.

제약 조건

1. 한 번에 한개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
3. 이동 횟수는 최소가 되어야 한다.

출력 양식

1. 첫째 줄에 옮긴 횟수 K를 출력한다.
2. 두 번째 줄부터 수행 과정을 출력한다.
   • K개의 줄에 걸쳐 두 정수 A B를 빈칸을 두고 출력한다.
   • A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻.

발상

• 가장 밑에 원판이 목적지에 가려면 그 원판을 제외한 나머지 원판들은 순서대로 목적지가 아닌 다른 곳에 쌓여 있어야 한다

• 재귀는 두가지로 분기 된다.

  1. 가장 밑 (N번째) 원판이 목적지로 가는 재귀
  2. 그 다음번째 원판들( 1~(N-1) )이 목적지로 가는 재귀

• 가장 큰 원판이 움직일 수 있도록 나머지 원판들이 경유지로 비켜주고 가장 큰 원판이 움직인다.

• 포인트는 각 재귀의 깊이 마다 목적지와 경유지가 바뀐다는 사실을 인지하는 것이다.

• 원판의 개수가 짝수인지 홀수인지에 따라서도 처음 움직이는 원판의 위치도 달라진다.

구현

    import java.util.Scanner;

    public class Num11729 {
        //하노이 타워
        static int cnt = 0;
        public static void rec(int num, int from, int by, int to, StringBuilder sb){
            if (num == 0) return;
            rec(num-1, from, to, by, sb); //n-1개의 원판을 가운데로 옮겨 주고
            cnt++;
            sb.append(from)
                .append(" ")
                .append(to)
                .append("\n");
            rec(num-1, by, from, to, sb);//남은 n-1개의 원판을 목적지로 옮겨 준다.
        }

        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            StringBuilder sb = new StringBuilder();
            rec(n, 1,2,3, sb);
            System.out.println(cnt);
            System.out.println(sb.toString());
        }
    }

결과