문제 번호 11729번 : 하노이 탑 이동 순서 - JAVA [자바]

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

11729번: 하노이 탑 이동 순서

 

문제 설명

 

하노이 탑을 이동하는 순서를 재귀를 사용하여 출력하는 문제입니다.

 

문제 풀이

 

재귀는 정말 어려운거 같습니다.

하노이 탑은 유명한 재귀 문제임으로 알아두도록 합시다.

이 문제의 핵심은 위에 가장 아래 탑을 옮기기 위해 어떤 행동을 해야 하는 지를 생각하는 것입니다.

위와 같은 하노이탑이 있다고 가정해 보겠습니다.

3번 탑을 옮기기 위해서는 어떤 행위를 해야하나요?

물론 1번을 옮기고 2번을 옮기고 1번을 다시 2번에 옮기고 이런 세세한 작업들이 있지만 그렇게 생각하면 재귀를 풀기 힘듭니다. 크게 어떤 행위를 해야 3번을 옮길 수 있는지 생각해보겠습니다.

 

네 맞습니다. 1,2 탑을 옆으로 먼저 옮겨야 합니다. 그래야 3번을 다른 칸으로 옮길 수 있을 테니깐요.

그게 첫번째 행동입니다. 재귀를 만들 때 n-1개의 옮겨야 하는 목표가 아닌 다른 칸으로 옮긴다. 이것을 기억하고 다음 행동을 생각해 보겠습니다.

 

네, 다음 행동은 당연히 3번 탑을 목표 칸으로 움직이는 것입니다. 결국에는 가장 높은 숫자의 탑이 하나 남았을 때 목표 칸으로 움직이는 것이 목표이니깐요. 그 후에 행동은 당연히 아래와 같습니다.

 

나머지 탑을 모두 목표 칸으로 옮기는 것입니다.

 

정리하면 하노이 탑 구현은 총 3가지 단계로 나눕니다.

1. n-1개의 탑을 목표 칸이 아닌 다른 칸으로 옮긴다.

2. n번째 탑을 목표 칸으로 옮긴다.

3. 나머지 탑을 모두 목표 칸으로 옮긴다.

이 3가지를 나누고 나눠서 1일때부터 실행하도록 하면 하노이탑 재귀가 완성됩니다.

이런 질문이 있을 수 있습니다.

결국에는 1의 탑을 옮기고 2번탑을 옮기고 1번 탑을 2번 탑 위에 놓고 이런 과정이 필요한데 신경쓰지 않아도되나요?

네 신경쓰지 않으셔도 됩니다. 결국에는 위에 과정을 쪼개서 반복하는 것 뿐입니다.

위에 사진을 보시면 1,2탑을 다른 칸으로 옮기게 되는데 이 때 재귀로 들어가 1,2번 탑을 똑같은 형식으로 옮기게 됩니다.

이때 목표 칸으 맨 오른쪽 칸이 아닌 중간 칸이 되겠죠.

똑같이 2번 탑을 중간 칸으로 옮기기 위해서는 2번 보다 위에 있는 모든 칸을 목표 칸이 아닌 다른 칸으로 옮기게 됩니다.

그리고 2번 탑을 목표칸으로 옮깁니다.

그리고 나머지 2번 탑을 제외한 나머지 탑을 모두 중간 칸으로 옮깁니다.(당연히 3번 탑은 제외입니다. 지금은 2번의 재귀 안으로 들어와서 욺직이는 것을 말하고 있으니깐요) 결국에 보면 위에 순서를 똑같이 진행한 것을 알 수 있습니다.

1. n-1개의 탑을 목표 칸이 아닌 다른 칸으로 옮긴다.

2. n번째 탑을 목표 칸으로 옮긴다.

3. 나머지 탑을 모두 목표 칸으로 옮긴다.

이 과정에서 옮기는 순간에 재귀를 호출해 나눠서 진행하면 하노이 탑을 구현할 수 있습니다.

import java.util.Scanner;

public class Number_11729 {

    public static StringBuilder stb = new StringBuilder();
    public static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Hanoi(n,1,2,3);

        System.out.println(count);
        System.out.println(stb);
    }

    private static void Hanoi(int n, int from, int via, int to){
        //가장 위에 있는 탑을 옮기는 과정
        if(n==1){
            count++;
            stb.append(from + " " + to + "\n");
            return;
        }
        //n-1 있는 탑을 옮기는 과정
        Hanoi(n-1, from, to, via);
        count++;
        stb.append(from + " " + to + "\n");
        //n-1의 탑을 n탑 위에 올리는 과정
        Hanoi(n-1, via, from, to);
    }
}

주석을 보면 위에 그림의 순서대로 되어 있음을 알 수 있습니다.

n-1의 탑을 옮길 때 to와 via를 바꾸는 이유는 가장 밑에 있는 탑이 목표 칸으로 옮겨지기 위해서는 n-1은 서브 칸으로 옮겨져야 하기 때문입니다.