[백준] 11729: 하노이 탑 이동 순서 (재귀를 푸는 사고 흐름 고치기) - JAVA

백트래킹을 공부해볼까 하다가 재귀를 먼저 학습했다. 정말 유명한 문제이지만, 재귀를 공부하면서 풀어보았다. 이번 게시글은 하노이 자체보다는 재귀를 공부한 내용에 초점을 맞춰볼까 한다.

 

원래 나는 재귀를 풀 때, 코드 흐름을 계속 따라들어가면서 풀었다. 그래서 복잡한 문제를 만나면 풀기 힘들고 이해가 전혀 되지 않았다. 이걸 견뎌내면서 모두가 풀고 있는 줄 알았는데 공부를 하면서 귀납적 풀이라는 걸 알게 되었다.

 

수학을 공부할 때 나오는 귀납법과 같다고 생각하면 된다.

 

귀납법

1. BaseCase에서 명제가 참
2. N일 때 명제가 참이라고 가정
3. 위 가정을 이용해 N+1일때도 명제가 참임을 증명

 

 

즉, 절차지향적으로 코드를 따라들어가는 게 아니라, 가능하다는 걸 전제하고 문제풀이를 진행하는 방식인 것이다.

하노이 문제에서 한 번 확인해보자.

 

https://www.acmicpc.net/problem/11729

 

 

 

# 문제

 

우선 기둥은 1, 2, 3 으로 세 개이다. 1에서 3으로 넣는다고 가정하면, start = 1, end = 3으로 잡았고 남은 기둥은 6 - start - end로 잡았다. 이제 재귀를 이용해서 원판을 옮기는 걸 상상해보자.

 

문제의 조건에 따라 맨 아래에 가장 큰 원판을 두어야 한다. n개의 원판이 1번에 꽂혀있다면, 우선 n - 1개의 원판을 2번에 옮긴다.

이때, 절차지향으로 생각하면 '여러개를 어케 옮겨' 라고 생각할 수 있으나, 정상적인 방법으로 2번 기둥으로 어찌어찌 옮겼다고 가정하는거다. 어차피 그렇게 옮기고 가장 큰 원판을 3번으로 옮기는 방식으로 구현해야한다.

 

옮기고 나면 n번째 원판을 3번 기둥으로 옮긴다. 

그 이후에는 n - 1개의 원판을 3번으로 옮기는 거다. 과정을 생략하고 생각해서 이상한거지 결론적으로는 맞으니까! 가능하다.

 

즉, 원판이 n - 1개일 때 옮길 수 있다면, 원판이 n개일 때도 옮길 수 있는 것이다. 원판이 1개 일때 또한 자명하게 내가 원하는 곳으로 옮길 수 있다. 따라서 귀납적 접근이 가능하게 된다.

 

이를 재귀 코드로 짜면 된다. 어려울 거 없이

1. n이 1일때 (basecase) -> 그냥 출력하면 끝

2. n - 1개를 2번으로 옮기기

3. n번 판을 3번으로 옮기기

4. n - 1개를 3번으로 옮기기

 

이거만 작성하면 되는 것이다.

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
    static StringBuilder sb = new StringBuilder();
    static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        hanoi(1, 3, N);
        System.out.println(cnt);
        System.out.println(sb);
    }

    private static void hanoi(int start, int end, int N) {
        if (N == 1) {
            sb.append(start).append(" ").append(end).append("\n");
            cnt++;
            return;
        }
        hanoi(start, 6 - start - end, N - 1);
        sb.append(start).append(" ").append(end).append("\n");
        cnt++;
        hanoi(6 - start - end, end, N - 1);
    }
}

 

처음에 너무 어렵게 생각됐는데, 귀납적으로 접근하니 한결 편안해진 게 느껴졌다! 재귀 문제들을 더 풀어보면서 사고 정리하는 시간을 계속 가져봐야겠다!

 

# 결과