[백준] 하노이 탑 이동 순서 (11729번)

문제 흐름

1. 목표: 주어진 n개의 원판을 첫 번째 기둥(스택)에서 세 번째 기둥으로 옮기는 것이 목표입니다. 단, 한 번에 한 개의 원판만 옮길 수 있으며, 큰 원판이 작은 원판 위에 놓일 수 없습니다.
2. 출력:
   • 최소 이동 횟수를 출력합니다.
   • 각 이동 경로를 (from, to) 형식으로 출력합니다.

 

핵심 아이디어

• 재귀적 접근:
  • 원판이 1개일 때는 바로 목표 기둥으로 옮기면 됩니다.
  • 원판이 여러 개일 경우, 재귀적으로:
    1. 상위 원판 n-1개를 보조 기둥으로 이동합니다.
    2. 가장 큰 원판을 목표 기둥으로 이동합니다.
    3. 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동합니다.
• 스택 사용: 각 기둥은 스택으로 구현되어, 원판 이동 시 올바른 순서를 유지합니다.

 

알고리즘 흐름

1. 초기화 (initHanoi):
   • 세 개의 기둥(스택)을 초기화합니다.
   • 첫 번째 기둥에 큰 원판부터 작은 원판까지 쌓아둡니다.
2. 하노이 함수 (hanoi):
   • 재귀 호출을 통해 원판을 옮기는 과정을 구현합니다.
   • 원판이 하나일 경우, 즉시 이동합니다.
   • 여러 개일 경우, 보조 기둥을 사용해 두 단계로 나누어 이동합니다:
     1. n-1개의 원판을 보조 기둥으로 이동.
     2. 가장 큰 원판을 목표 기둥으로 이동.
     3. 다시 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동.
3. 원판 이동 (moveDisk):
   • from 기둥에서 to 기둥으로 원판을 옮기고, 이동 기록을 저장합니다.
   • 각 이동 시마다 이동 횟수를 증가시킵니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Main {

    // 원판의 개수
    static int n;

    // 이동 횟수 카운트
    static int count = 0;

    // 각 기둥을 표현하는 3개의 스택 배열 (0: 시작 기둥, 1: 보조 기둥, 2: 목표 기둥)
    static Stack<Integer>[] stack = new Stack[3];

    // 이동 경로를 기록하는 StringBuilder
    static StringBuilder recode = new StringBuilder();

    // 이동 경로 출력 형식 (예: "1 3\n"은 1번 기둥에서 3번 기둥으로 이동)
    static final String format = "%s %s\n";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); // 원판 개수 입력

        // 초기 기둥 상태 설정 (첫 번째 기둥에 모든 원판 쌓기)
        initHanoi();

        // 하노이 탑 알고리즘 수행 (n개의 원판을 0번 기둥에서 2번 기둥으로 이동)
        hanoi(n, 0, 2, 1);

        // 총 이동 횟수와 경로를 출력
        System.out.println(count);
        System.out.println(recode);
    }

    /**
     * 하노이 탑 재귀 함수
     * @param disk 이동할 원판의 수
     * @param from 시작 기둥
     * @param to 목표 기둥
     * @param aux 보조 기둥
     */
    public static void hanoi(int disk, int from, int to, int aux) {
        // 원판이 하나일 때는 바로 목표 기둥으로 이동
        if (disk == 1) {
            moveDisk(from, to); // 이동 수행
            return;
        }

        // (1) 상위 n-1개의 원판을 보조 기둥으로 이동
        hanoi(disk - 1, from, aux, to);

        // (2) 가장 큰 원판을 목표 기둥으로 이동
        moveDisk(from, to);

        // (3) 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동
        hanoi(disk - 1, aux, to, from);
    }

    /**
     * 원판을 한 기둥에서 다른 기둥으로 이동하고 기록
     * @param from 시작 기둥
     * @param to 목표 기둥
     */
    public static void moveDisk(int from, int to) {
        stack[to].push(stack[from].pop()); // 원판 이동
        count++; // 이동 횟수 증가
        recode.append(String.format(format, from + 1, to + 1)); // 이동 경로 기록
    }

    /**
     * 3개의 기둥(스택)을 초기화하고 첫 번째 기둥에 원판을 쌓는 함수
     */
    public static void initHanoi() {
        // 3개의 기둥(스택) 초기화
        for (int i = 0; i < 3; i++) {
            stack[i] = new Stack<Integer>();
        }

        // 첫 번째 기둥에 원판 쌓기 (큰 원판이 아래로 가도록 n부터 1까지)
        for (int i = n; i >= 1; i--) {
            stack[0].push(i);
        }
    }
}