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

문제 url:
하노이 탑 이동 순서

문제:

🤔 문제 알아보기

---

필자는 몰랐는데, 하노이의 탑은 재귀문제로 유명한 예제라고 하며, 공식 역시 유명하다고 한다.

두괄식으로 먼저 설명하자면 총 하노이 탑 이동 횟수는 $2^N - 1$의 값을 가진다고 한다.

그럼 왜 이동 횟수가 $2^N - 1$가 되는지 한번 살펴보자,

원판이 3개 일때, 그림을 그리면 위와 같다.

여기서, 우리는 1번 기둥 -> 3번 기둥으로 가고자 한다.
문제 조건에서, 쌓아놓은 원판의 위는 아래보다 작아야 한다고 하는데,
그럼, 숫자 3인 원판을 3번 기둥까지 가기 위해서는 N-1개 만큼 원판을 움직어야 한다.

그림 센스가 별로라 조금 그렇다...

N개의 원판을 1번 기둥에서 3번 기둥으로 옮길 때
$a_n = a_{n-1} + 1 + a_{n-1}$ -> $a_n = 2(a_{n-1}) + 1$만큼 될 것이다.
※여기서, 1을 더한 이유는 1번 기둥에서 2번 기둥으로 N-1개만큼 옮긴 후,
1번에 남은 마지막 원판을 1번 -> 3번으로 이동하는 과정이 1번만 이루어 지기 때문에 해당 횟수를 더한다.

여기서 우리가 구할 수 있는 것은 총 두개가 존재한다.
먼저, 첫 번째 원판은 반드시 1이다. 그래서 이를 구하면 $a_1 = 1$이 된다.

또한, 위에서 구한 $a_n = 2a_{n-1}$은 곧 $a_{n+1} = 2a_n + 1$과 동일하다.

자 우리는 해당 점화식으로 부터 등비수열을 얻어 해당 점화식에서 일반항을 찾아보자,
그러기 위해서는 각 항에 +1씩 하여 다음과 같이 구할 수 있다. $a_{n+1} + 1 = 2(a_n + 1)$

그리고 임의의 값 $b_n$이 다음과 같다면,
$b_n = a_n + 1$ -> $b_{n+1} + 1 = 2b_n$

우리는 이를 통해 등비가 2임을 알 수 있다.

그럼, $a_n +1 = b_n$ 여기서 $b_n은 2^n$ 과 동일하기 때문에
따라서 일반항 $a_n = 2^n -1$이 나올 수 있는 것이다.

필자는 수학을 못한다.. 그래서 여러 하노이의 탑 공식을 찾아보면서 이해 해봤는데,
이를 문제에서 이해하고자 하면 엄청 어려울 것 같다.
그리고, 설명이 좋지 않아 이해하기 어렵다면, 아래의 두 링크를 확인하면 좋을듯 하다
[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바] Stranger's LAB

하노이탑 공식 유도

자 그러면, 총 이동 횟수까지는 구하였다.
그럼 출력 둘 째줄부터는 이동 경로를 표현해야 하는데, 이는 코드와 함께 알아보겠다.

🐱‍👤 실제 코드

---

import java.io.*;

public class Main {
    static StringBuilder sbd;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sbd = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

		// 하노이 탑 이동 횟수
        sbd.append((int)Math.pow(2,N)-1).append("\n");

        hanoi(N, 1, 2, 3 );

        System.out.println(sbd);
    }
    static void hanoi(int N, int start, int mid, int end) {

        /*
         * N이 한개 남았다는 것은 곧 제일 밑에 있는 원판을
         * A -> C로 움직여야 한다는 의미
         */
        if(N == 1) {
            sbd.append(start + " " + end).append("\n");
            return;
        }

        /*
         * 원판을 A -> B로 움직이는 재귀호출
         */
        hanoi(N-1, start, end, mid);

        sbd.append(start + " " + end).append("\n");

        /*
         * 원판을 B -> C로 움직이는 재귀 호출
         */
        hanoi(N-1, mid, start, end);
    }
}

hanoi 메서드는 먼저, 원판 개수 N과 이동해야 할 기둥 숫자를 입력받는다.

주석에도 설명이 되어 있지만, 이를 같이 한번 해보면서 살펴보자

💢 재귀함수 호출 알아보기

---

main 클래스에서 처음 호출 될 때 hanoi(N, 1,2,3)을 입력받는다.
그럼 현재 start: 1, mid: 2, end:3인 것이다.

N이 1이라면, 마지막 원판을 1기둥에서 3기둥으로 옮겨야 하기 때문에
아래의 로직을 구현한 것이다.

		if(N == 1) {
            sbd.append(start + " " + end).append("\n");
            return;
        }

자 그럼, 마지막 원판만 남기기 위해 원판을 이동시켜보자,

hanoi(N-1, start, end, mid);

현재, N이 3이고 start: 1, mid: 2, end: 3이라고 가정하자,

N = 2 인 재귀상황

N이 2일 때 start : 1, mid: 3, end: 2로 진입, N이 1이 아니기 때문에 다시 재귀 호출

hanoi(N-1, start, end, mid);

N이 1일 때 start: 1, mid: 2, end: 3으로 진입, N이 1이기 때문에
1, 3을 출력될 것이다. 그런 다음 return에 의해 다시 N이 2일때로 이동

sbd.append(start + " " + end).append("\n");

해당 코드를 출력하면서, 1, 2를 출력

마지막으로 아래 코드를 재귀 호출

hanoi(N-1, mid, start, end); (2, 3, 1, 2)이 들어감

현재 N=1 , start: 2, mid: 1, end:3 상황에서 N이 1이기 때문에 이를 출력하면, 3, 2을 출력

그러면, 이제 N = 2 인 경우의 모든 재귀 호출은 마무리 되었다.

그러면 다시 돌아가 N = 3인 경우일 때의 hanoi 메서드 호출에 대해서 살펴보자면,

N = 3인 재귀 상황

sbd.append(start + " " + end).append("\n");

해당 코드를 호출하여 1,3을 호출

그런 다음 마지막 B-> C로 이동하는 재귀호출을 진행

hanoi(N-1, mid, start, end); (3, 2, 1, 3)이 입력됨

그럼 현재 기준 N = 2, start: 2, mid: 1, end: 3
여기서 N이 1이 아니기 때문에 다시 재귀호출을 진행

hanoi(N-1, start, end, mid); (1, 2, 3, 1)이 입력됨

그러면 N이 1이기 때문에 2,1을 호출하며 return

그 후 아래 로직을 차례로 진행하면

		sbd.append(start + " " + end).append("\n");

        /*
         * 원판을 B -> C로 움직이는 재귀 호출
         */
        hanoi(N-1, mid, start, end);

다음과 같은 결과를 얻을 수 있다.

🤢 회고

---

재귀 파트의 마지막 문제이다!
비전공자인 필자도 처음에 알고리즘을 알아갈때 어느 한 블로그에서 코테 문제로 해당 문제가 나온적 있었다는 것을 보고 이름 정도는 기억하고 있었는데 이 문제를 직접 풀어본다니, 약간 감격이었다.

그러나.. 문제가 역시 쉽지 않다... 아직까지는 재귀에 대해서 이해도가 낮은듯하다 머리로는 설계가 쉽지 않다

💜 참고자료

---

[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바] Stranger's LAB