백준 11729 하노이 탑

문제

리뷰

내 생각

문제 파악을 잘 못하였다. 재귀함수를 써야한다는 것은 알겠지만 어떻게 구현해야 하는지 해멨다.
스택을 활용해야 하나 생각했는데 그러자니 더 복잡해졌다.
결국 인터넷의 힘을 빌렸다.

풀이

괜히 개수를 크게 생각해보니 머리가 더 복잡해져 단순하게 2개의 원판만을 놓고 생각을 해보았다.
그 이후에는 결국 같은 패턴의 연속이다.
다음과 같이 2개의 원판을 3으로 옮기고자 한다면,

1. 원판1을 먼저 2번으로 옮겨야한다(경유지).

2. 원판2를 3번으로 옮긴다(목적지).

3. 원판1을 3번으로 옮긴다(목적지).

코드

public class Q11729 {

    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        sc.close();
        
        // 이건 n개의 원판을 다른 위치로 옮기고자 할때 걸리는 횟수를 구하는 공식
        sb.append((int)(Math.pow(2,cnt)-1)).append("\n");

        hanoi(cnt, 1, 2, 3);
        System.out.println(sb);
    }
    
    //from은 기존 위치
    //sub는 중간에 경유할 위치
    //to는 목적지
    //n은 원판의 개수
    // n이 2라고 가정해보자
    public static void hanoi(int n, int from, int sub, int to){
        if (n==1){
            sb.append(from + " "+ to + "\n");
            return;
        }
        // 원판1을 경유지로 이동
        hanoi(n-1,from,to,sub);
        // 원판2를 목적지로 이동
        sb.append(from + " " + to + "\n");
        // 원판1을 목적지로 이동
        hanoi(n-1,sub,from,to);
    }

}

• 원판이 2개라고 가정했을 때 출력 결과,
  
• 원판이 3개라고 가정했을 때 출력 결과,