Baekjoon | Q.11729 - 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

 세 개의 장대의 첫 번재 장대에는 반경이 서로 다른 n개의 원판이 쌓여있고 각 원판은 반경이 큰 순서대로 쌓여있다. 한번에 한 개의 원판만을 옮기며 어느 장대든 반경이 큰 순서대로 쌓여있어야 한다. 이 때, 마지막 장대로 모든 원판이 옮겨지는 경로를 구하는 문제이다.

 

package step10.p11729;

import java.util.Scanner;

class Main {
    
    static int count = 0;
    static StringBuilder sb = new StringBuilder();

    static void Hanoi(int n, int from, int by, int to) {
        count++;
        // n == 1이면 A에서 C로 이동
        if(n == 1) sb.append(from + " " + to + "\n");
        else {
            // n번째 원반을 옮기기 위해 n-1개를 A에서 B로 이동..
            Hanoi(n-1, from, to, by);
            // n번째의 원반을 C로 이동
            sb.append(from + " " + to + "\n");
            // 다시 B로 이동한 n-1개의 원반을 이제 C로 이동시킨다.
            Hanoi(n-1, by, from, to);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Hanoi(n, 1, 2, 3);
        sb.insert(0, count + "\n");

        System.out.println(sb);

        sc.close();
    }
}

 

 재귀함수를 이용하여 풀어야 하는 문제인데 해결을 하지 못하여 인터넷 풀이과정을 읽어보았다..ㅠㅠ

 

 세 장대를 A B C, 원반을 한번 이동시키는 메소드를 Hanoi() 라고 하자. A에 위치한 n개의 원판 중 n번째의 원반을 C로 옮기고자 한다면 n-1개의 원판을 C를 거쳐 B로 옮기는 선행 과정이 필요하다. 그 후 n번째의 원반을 C로 이동시키고 B로 이동된 n-1개의 원반을 A를 거쳐 C로 이동시키면 된다.

 

 출력은 StringBuilder를 이용하여 문자열을 마지막에 한번에 출력시켜주었다.