[백준 *Java] - 하노이 탑 이동 순서(11729)

하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

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

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

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

 

---

접근 방식

코드를 재귀적인 설계를 한다는 게 확실히 어려웠습니다.
처음에 로직 설계는 자료구조 스택을 이용해서 세 개의 peg에서 제일 위에 있는 disc 를 가지고 남은 이동할 수 있는 두 peg 에 어떤 식으로 옮겨야 할까 생각했습니다.
이렇게 할 시에, 재귀적으로 설계를 한다는 게 깔끔하지 않고 복잡해지기만 하고 로직 설계가 마무리 되어가는 게 아닌, 더 복잡해지는 거 같았습니다.

재귀적으로 구현하는 게 아직 트레이닝이 덜 됐다는 걸 느꼈던 거 같습니다.

주의 해야할 점은,
총 discs 를 가지고 재귀를 돌려주는데, 가장 큰 disc에서 작은 disc를 갈 수 있게끔 callstack을 쌓아주고, callback 하는 과정에서 이동 했다고. 이동한 상태 문자열을 만드는 식으로 구현합니다.

재귀 process

 

아래는 구현한 코드입니다. 

 

import java.util.Scanner;

public class Boj_11729 {
    static StringBuilder sb = new StringBuilder();
    static int cnt;

    public static void hanoi(int nDisks, int fromPeg, int toPeg) {
        if (nDisks == 1) {
            move(fromPeg, toPeg);
            return;
        } else {
            int helpPeg = 6 - fromPeg - toPeg; // 보조 peg
            
            hanoi(nDisks - 1, fromPeg, helpPeg);
            move(fromPeg, toPeg);
            hanoi(nDisks - 1, helpPeg, toPeg);
        }
    }

    public static void move (int fromPeg, int toPeg) {
        sb.append(fromPeg).append(' ').append(toPeg).append('\n');
        cnt++;
        return;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        hanoi(N, 1, 3);
        System.out.println(cnt);
        System.out.println(sb);
    }
}