<Algorithm> 202. 하노이 탑 이동순서(BJO)

1. 11729번 하노이 탑 이동순서(BJO)

   사용 알고리즘 :  재귀, 분할정복

• 코드는 간단하지만 이해가 필요한 문제인 것 같다. 2차원 배열 이외에 이런 분할정복은 처음인데 많이 해봐야 겠다.

• 또 단순 println 했을경우 시간초과가 발생해서 StringBuilder를 사용했다. 이부분에서 속도를 줄일 수 있기 때문에 중요한 부분이다.

문제에 대한 접근&생각

1. 순서대로 쌓여있는 탑을 3번째 탑으로 이동 시켜야함 -> 직접해보면 n-1 번쨰 까지 탑을 두번째로 옮겨야함 -> 재귀!
2. 이후에 n번째 탑을 3번으로 옮김 -> 2번상에 대해 위의 동작을 반복

코드 

import java.util.Scanner;
 
public class Main {
    static StringBuilder sb = new StringBuilder("");
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /******************************
         * 재귀를 이용하여 n-1 번쨰까지 
         * 2번 단상으로 옮기고
         * n번째를 3번 단상으로 옮긴후
         * 다시 2번 단상에서 3번단상으로 옮기는
         * 순서를 구한다.
         *******************************/
        int n = sc.nextInt();
        System.out.println((1<<n)-1);
        move(n, 1, 3);
        System.out.println(sb);
    }
    private static void move(int n, int a, int b) {
        if(n==0) return;
        move(n-1, a, 6-a-b);
        sb.append(a+" "+b).append("\n");
        move(n-1, 6-a-b, b);
    }
}
 

참고 & 출처  

http://blog.naver.com/PostView.nhn?blogId=puri8467&logNo=221440092130&from=search&redirect=Log&widgetTypeCall=true&directAccess=false

https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/pc/challenge-solve-hanoi-recursively