Baekjoon #11729 하노이 탑 이동 순서

하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. (이미지는 위 URL에서 확인)

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

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

---

점화식을 이용해서 풀 수도 있는 문제지만 직관적으로 패턴을 이용해 풀었다.

 

패턴

패턴

패턴2

입력 받은 위치를 a, b, c라고 했을 때, 가운데 부분은 항상 출력이므로 a 와 c 자리를 출련한다.

패턴을 보면 가운데 옮기기 윗쪽으로는 b와 c만 위치가 바뀐모양이고

아랫쪽으로는 a와 b만 위치가 바뀐 모양이다.

 

따라서 이 패턴을 함수로 작성한다면

hanoi(a, b, c) 입력 hanoi(a, c, b) print(a c) hanoi(b, a, c)

재귀적 호출을 통해 풀 수 있다.

 

언제까지 재귀 호출을 할 것인가?

탑의 높이(n)이 0이 될 때까지 호출 하면 되고, 하나씩 전개해 나갈 때마다 n-1을 해주면 된다.

public static void hanoi(int n, int a, int b, int c) {
    if (!(n-1 == 0)) {
        hanoi(n-1, a, c, b);
    }
    sb.append(a + " " + c + "\n");
    if (!(n-1 == 0)) {
        hanoi(n-1, b, a, c);
    }
}

---

/*
* 하노이 탑
* https://www.acmicpc.net/problem/11729
* */

import java.util.Scanner;

public class P11729 {
    public static StringBuilder sb = new StringBuilder();

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

        int n = sc.nextInt();
        sb.append((int) Math.pow(2, n) - 1).append("\n");
        hanoi(n, 1, 2, 3);
        System.out.println(sb);

        sc.close();
    }


    public static void hanoi(int n, int a, int b, int c) {
        if (!(n-1 == 0)) {
            hanoi(n-1, a, c, b);
        }
        sb.append(a + " " + c + "\n");
        if (!(n-1 == 0)) {
            hanoi(n-1, b, a, c);
        }
    }
}