[BaekJoon/백준] 11729번

하노이탑을 재귀함수로 구현하라는 문제다.

 

하노이탑을 혼자 스스로의 힘으로도 해결하지 못하는데 규칙을 찾아 코드로 구현하라니 정말 나에게는 말이 안되는 난이도다.

문제를 알아가면서, 덕분에 하노이 탑의 규칙성에 대해서도 알게됐다.

 

하노이 탑의 이동규칙은 다음의 3개이다.

 

1. N-1개의 원판을 경유지 기둥에 이동

2. 가장 큰 1개의 원판을 목적지 기둥에 이동

3. 경유지 기둥에 있던 N-1개의 원판을 목적지 기둥에 이동

 

원판이 몇개이던 간에 이전 갯수의 원판의 이동과 연관이 있다. 그렇게 재귀를 구현할 수 있다.

 

따라서 하노이 탑의 횟수 식 또한

An = 2A(n-1) +1 이라고 볼 수 있고, 이를 계차수열의 일반항 공식으로 풀어주면

탑이 N개일 때 2^N -1 횟수의 규칙을 갖는다.

 

 

이 문제를 생각할 때, 탑이 두개 이상일 때 갯수에 상관없이 항상 두개일 때로 묶어서 생각해주면 쉽다.

탑이 5개이면 4개를 하나로 묶어서 생각하여 총 2개의 원판을 옮기는 과정이라고 생각하면 된다.

그리고 4개의 원판을 옮기는 과정은 재귀함수로 풀어주는것.

또 4개의 원판을 옮기는 재귀함수 안에서는, 3개의 원판을 하나로 묶어서 총 2개의 원판을 옮기는 과정인 것이다.

 

그리고 전체 재귀함수의 코드는 '1개일 때' (탈출조건) 와 '2개일 때' (재귀조건) 의 처리로 해결한다.

 

'상대적인' 이동은 원판이 2개일 때부터 시작되므로, 원판이 1개일 때엔 그냥 움직여주는 코드만 작성해주면 되고

이 1개일 때의 조건이 재귀함수를 탈출하는 조건이다. (두개부터 재귀함수가 실행된다.)

 

문제상에서는 기둥과 기둥 사이를 공백으로 요구하는데, 눈에 보기 쉽게 예시로 화살표를 넣었다.

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class hanoi {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String args[]) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        bw.write(""+(int)(Math.pow(2, N)-1)+"\n"); //2의 n승 -1횟수다.
        hanoi_(N, 1, 3);
        bw.flush(); bw.close();
    }

    public static void hanoi_(int t, int from, int to) throws Exception{
        if(t==1) {
            bw.write("" + from + " -> " + to+"\n");
            return;
        } else {
            int temp = 6 - from - to; // 탑은 1 2 3이 있으므로 6에서 빼면 남은 한 개의 탑이 나옴.
            hanoi_(t-1, from, temp); //n-1개를 경유지 기둥에 보냄
            bw.write("" + from + " -> " + to+"\n"); //1개의 기둥을 목적지 기둥에 보냄
            hanoi_(t-1, temp, to); //보내놨던 n-1개를 목적지 기둥으로 보냄
        }
    }
}

 

묶어서 생각하는것. 그것이 재귀의 목적이자 이유이다.

재귀 = 탈출조건 + 재귀조건 ( 재귀방식 구현 시 묶어서 생각 )

 

하노이탑 코드는 두고두고 계속 봐야겠다.

 

 

p.s

참고로 어떤 분이 너무 잘 설명해주셨길래 첨부해본다...

haams704.tistory.com/54

하노이탑 알고리즘