[백준 JAVA] 11729 : 하노이 탑 이동 순서

[백준 11729] 하노이 탑 이동 순서 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

 

문제 조건 정리

 

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
3. 이동 횟수는 최소가 되어야한다.

---

입력

 

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

---

문제를 풀기 전

 

1. 재귀로 유명한 하노이 탑 문제라서 재귀로 해결해야겠다고 생각했음!
2. 스트링빌더의 맨 처음에 카운트 값을 넣어야하는 방법을 사용하기보다 카운트 값을 출력하고 이동 순서를 출력해야겠다고 생각함!

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static StringBuilder stringBuilder = new StringBuilder();
    static int count = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        hanoi(n, 1, 2, 3); // n개의 판을 1번에서 2번을 거쳐서 3번으로 이동시키자.

        System.out.println(count);
        System.out.println(stringBuilder);

    }

    private static void hanoi(int n, int start, int mid, int end) {

        count++; // 이동할 때마다 카운트 값 증가

        // (남은)판이 하나라면 바로 옮긴다. (시작 -> 목적지)
        if (n == 1) { 
            stringBuilder
            .append(start)
            .append(" ")
            .append(end)
            .append("\n");
        } 
        // 하나가 아니라면
        else {
            // 옮겨야하는 판에서 하나를 제외하고 목적지를 거쳐서 경유지로 이동
            // 옮겨야하는 판들 중에서 가장 큰 판만 시작 지점에 남은 상태
            hanoi(n - 1, start, end, mid);
            
            // 위의 과정으로 가장 큰 판만 시작 지점에 남았고,
            // 경유지에 모든 판들이 쌓인 상태
            // 시작 지점의 가장 큰 판 하나를 목적지로 보낸다고 기록
            stringBuilder.append(start).append(" ").append(end).append("\n");
            
            // 이제 경유지에 있는 n-1개의 판을 시작 지점을 거쳐서 목적지로 보냄
            hanoi(n - 1, mid, start, end);
        }
    }
}

 

---

문제를 풀고 난 후

 

재귀 문제를 풀 때마다, 재귀의 내부가 아름답기도 하지만 심연같이 깊게 느껴짐!

조건을 완벽히 이해했다면, 재귀적으로 식을 표현하는 것은 간단해보임!

하지만 재귀의 내부를 이해해야지만 진정 문제를 이해했다고 생각함!

이를 위해서 함수 호출 순서를 찍어봄!

 

checker
.append("hanoi 함수의 ")
.append(count+1).append("번째 호출 -> ")
.append(n).append("개의 판을 ")
.append(start).append("에서 ")
.append(mid).append("를 거쳐서 ")
.append(end).append("로 향하게 한다").append("\n");

 

입력값이 3인 경우
hanoi 함수의 1번째 호출 -> 3개의 판을 1에서 2를 거쳐서 3로 향하게 한다
    hanoi 함수의 2번째 호출 -> 2개의 판을 1에서 3를 거쳐서 2로 향하게 한다
        hanoi 함수의 3번째 호출 -> 1개의 판을 1에서 2를 거쳐서 3로 향하게 한다
        hanoi 함수의 4번째 호출 -> 1개의 판을 3에서 1를 거쳐서 2로 향하게 한다
    hanoi 함수의 5번째 호출 -> 2개의 판을 2에서 1를 거쳐서 3로 향하게 한다
        hanoi 함수의 6번째 호출 -> 1개의 판을 2에서 3를 거쳐서 1로 향하게 한다
        hanoi 함수의 7번째 호출 -> 1개의 판을 1에서 2를 거쳐서 3로 향하게 한다

 

입력값이 4인 경우

hanoi 함수의 1번째 호출 -> 4개의 판을 1에서 2를 거쳐서 3로 향하게 한다
    hanoi 함수의 2번째 호출 -> 3개의 판을 1에서 3를 거쳐서 2로 향하게 한다
        hanoi 함수의 3번째 호출 -> 2개의 판을 1에서 2를 거쳐서 3로 향하게 한다
            hanoi 함수의 4번째 호출 -> 1개의 판을 1에서 3를 거쳐서 2로 향하게 한다
            hanoi 함수의 5번째 호출 -> 1개의 판을 2에서 1를 거쳐서 3로 향하게 한다
        hanoi 함수의 6번째 호출 -> 2개의 판을 3에서 1를 거쳐서 2로 향하게 한다
            hanoi 함수의 7번째 호출 -> 1개의 판을 3에서 2를 거쳐서 1로 향하게 한다
            hanoi 함수의 8번째 호출 -> 1개의 판을 1에서 3를 거쳐서 2로 향하게 한다

    hanoi 함수의 9번째 호출 -> 3개의 판을 2에서 1를 거쳐서 3로 향하게 한다
        hanoi 함수의 10번째 호출 -> 2개의 판을 2에서 3를 거쳐서 1로 향하게 한다
            hanoi 함수의 11번째 호출 -> 1개의 판을 2에서 1를 거쳐서 3로 향하게 한다
            hanoi 함수의 12번째 호출 -> 1개의 판을 3에서 2를 거쳐서 1로 향하게 한다

        hanoi 함수의 13번째 호출 -> 2개의 판을 1에서 2를 거쳐서 3로 향하게 한다
            hanoi 함수의 14번째 호출 -> 1개의 판을 1에서 3를 거쳐서 2로 향하게 한다
            hanoi 함수의 15번째 호출 -> 1개의 판을 2에서 1를 거쳐서 3로 향하게 한다

 

 

재귀의 내부를 정확히 읽어보고 작은 도움이 됐으면 좋겠음!