[백준] 11729: 하노이 탑

이 문제를 풀기에 앞서 사전지식으로는 재귀함수에 대한 이해가 필요하다.

재귀

재귀 (Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다.

재귀함수의 특징

반드시 함수 안에 종료구간인 Base Case가 있어야함 (무한 호출방지를 위해)

예시) 무한루프에 빠지지 않게 Base case를 설정해준 예시

public class Recursion_Test3
{
    public static void main(String[] args)
    {
        Function(5);
    }
 
    public static void Function(int num)
    {
        if(num == 0)
        {
            return;
        }
        else
        {
            System.out.println("하위");
            Function(num - 1);
        }
    }
}

하노이탑 문제

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

• 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

• 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

test case 분석하기

n=2 일때

경우의 수1)
1번 원판(A) -> B
2번 원판(A) -> C
1번 원판(B) -> C

그럼 여기서 Base Case는 무엇일까요?
=> 마지막 원반인 n=1일때의 원반을 B에서 C로 옮길 때

n=3 일때

n-1일개의 원판을 비어있는 다른 축(목적지가 아닌)으로 옮긴다.(3번)
1번 원판(A) -> C
2번 원판(A) -> B
1번 원판(C) -> B

제일 큰 원판을 목적지로 옮긴다.
3번 원판(C) -> C

n = 2일때의 상황과 같다.(제일 큰 원반 위에 n-1개의 원반을 옮긴다)

1번 원판(B) -> A
2번 원판(B) -> C
1번 원판(A) -> C

총 7번 이동

이 시점에서 두 가지 규칙을 발견할 수 있습니다. 첫째는 바로 하노이 탑 문제를 재귀적으로 풀 수 있다는 것입니다.

첫번째 규칙

n=1 일때 1번 원반을 옮기면 됩니다.

n≥2 일 경우는 다음과 같은 세 단계에 걸쳐 문제를 풉니다:
1. 1번부터 n-1번 원반을 다른 비어있는 축으로 옮김(재귀적)
2. n번 원반을 최종적으로 옮겨야 할 축으로 옮김.
3. 1번에서 옮겼던 n-1개의 원반을 다시 최종적으로 옮겨야 할 축으로 옮김(재귀적)

두 번째 규칙

원판의 이동 횟수를 점화식을 통해 해결할 수 있다.
n 개의 원판을 이동시키기 위해 Hanoi(n-1) 횟수만큼 이동한 횟수가 2번이고,

가장 아래 원판은 1번 이동하였으므로 공식화 하면 아래와 같다.

𝑛개의 원판을 이동시키기 위한 이동 횟수를 $𝑎_{𝑛}$ 이라고 할 때 $a_{n+1}$의 경우를 보면

1. 가장 큰 𝑛 번째 원판을 옮기기 위해 $𝑛-1$ 개의 원판을 옮겨야 한다. 이 때 $𝑛$개의 원판이 A 에서 B 로 이동하는 경우는 $𝑎_{𝑛}-1$ 이다.

2. 𝑛 번째 원판을 A 에서 C 로 옮기는 경우는 1 이다.

3. B에 있는 n개의 원판이 C로 옮기는 경우는 $a_{𝑛}-1$이다.

$a_{𝑛} = a_{n-1}-1 + 1 + a_{𝑛-1}-1$
$a_{𝑛} = 2a_{n-1}-1$

이 식을 점화식으로 풀면


$b_{n}=a_{n}+1$이라고 하자. 표현 할 수 있다. 이는 곧 공비가 2임을 말한다.

첫째항은 2

첫째항이 2이고 공비가 2인 등비수열을 일반화한 수열은
$𝑎_{𝑛} = 2^n- 1$

원판이 1일떄 $2^1- 1 = 1$ (총 1번)
원판이 2일떄 $2^2- 1 = 3$ (총 3번)
원판이 3일떄 $2^3- 1 = 7$ (총 7번)
원판이 4일떄 $2^4- 1 = 15$ (총 15번)
원판이 5일떄 $2^5- 1 = 31$ (총 31번)

이를 바탕으로 코드를 짜면

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

public class hanoi_11729 {

    public static StringBuilder sb = new StringBuilder();

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

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

        sb.append((int) (Math.pow(2, N) - 1)).append('\n');

        Hanoi(N, 1, 2, 3);
        System.out.println(sb);

    }
 
	/*
		N : 원판의 개수 
		start : 출발지 
		mid : 옮기기 위해 이동해야 장소 
		to : 목적지
	 */

    public static void Hanoi(int N, int start, int mid, int to) {
        // 이동할 원반의 수가 1개라면?
        if (N == 1) {
            sb.append(start + " " + to + "\n");
            return;
        }

        // A -> C로 옮긴다고 가정할 떄,
        // STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
        Hanoi(N - 1, start, to, mid);

        // STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
        sb.append(start + " " + to + "\n");

        // STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
        Hanoi(N - 1, mid, start, to);
    }
}