백준 11729 하노이 탑 이동 순서 Java

분할 정복에서 유명한 문제인? 하노이 탑 이동 순서 문제이다.

정답률이 52퍼센트이다. 어떻게 52퍼센트인지 모르겠다..

나에겐 굉장히 어려웠고 답을 보고 난 정말 재능이 없다고 생각했다.

 

문제 자체는 간단하다.

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

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

첫 번째 탑에 있는 원판들을 전부 세 번째 탑으로 이동하는데

수행하는 작업의 최소 횟수와 그 경로를 출력하면 되는 문제이다.

 

원판은 n개 탑은 3개로 고정이다.

항상 위에 것이 가장 작고 옮길 때 위에 것 부터 가져가니까 스택으로 해결하면 될 것 이라고 생각했다.

그렇게 열심히 삽질을 했지만 실패했다.ㅠ

 

답을 구하려면

3가지 단계로 생각했어야 했다.

 

1. n-1개 만큼 2번째 판에 옮긴다

.

2. 1번째 판에 남은 가장 큰 원판을 3번째 탑에 옮긴다.

3. 2번째 판에 있는 n-2개의 원판을 3번째 탑에 옮긴다.

 

solve()라는 메소드를 x번째 탑에서 y번째 탑으로 n-1개 만큼 이동시키는 메소드라고 생각하고

public static void solve(int n, int x, int y, StringBuilder sb) {
        if (n == 0) return;
        solve(n-1, x, 6-x-y, sb); //1단계
        sb.append(x + " " + y + "\n"); //2단계
        solve(n-1, 6-x-y, y, sb); //3단계
    }

 if (n == 0) return; //n이 0 이면 리턴

solve(n-1, x, 6-x-y, sb); //n-1개를 x에서 6-x-y로 옮긴다.

sb.append(x + " " + y + "\n"); //x번째에 남은 가장 큰 판을 y로 옮긴다.

solve(n-1, 6-x-y, y, sb); //6-x-y에서 y로 n-1개를 옮긴다.

 

6-x-y는

1단계에서는 1번째 탑에서 2번째 탑으로 n-1개만큼을 옮겨놔야 하는데

처음 원판이 있는 x와

옮겨야 하는 판인 y를 제외한

다른 곳에 옮겨놔야 된다는 말과 같다.

탑의 개수가 3개밖에 없기 때문에 6에서 x를빼주고 y를 빼주면

나머지 옮겨놓을 곳이 나오게 된다.

 

이 메소드 하나면 Stringbuilder인 sb를 출력하는 것 만으로 문제가 해결된다.

나는 사실 이 메소드 설명에 대해서는 이해는 가지만

이론적으로만 완벽한 이 메소드가 어떻게 정답으로 이끌어주는지 자세히는 정말 모르겠다.

 

실행과정을 나열해봐도 정답은 출력하지만 이 메소드가 왜 정답인지는 잘 모르겠다.

아직 많이 부족한 것 같다. 문제만 보고 이 메소드를 생각해내는 사람이 있나 싶다.

문제에서는 실행 경로 뿐 아니라 실행 횟수도 출력해줘야 한다.

 

import java.util.Scanner;
 
public class Q11729 {
    static int cnt = 0;
 
    public static void solve(int n, int x, int y, StringBuilder sb) {
        if (n == 0) return;
        cnt++;
        solve(n-1, x, 6-x-y, sb); //1단계
        sb.append(x + " " + y + "\n"); //2단계
        solve(n-1, 6-x-y, y, sb); //3단계
    }
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        solve(n, 1, 3, sb);
        System.out.println(cnt);
        System.out.println(sb);
    }
}
 

실행 횟수는 2n+1로도 나타낼 수 있고

1<<n 으로도 나타낼 수 있다는데

이유는 모르겠다.

나는 나에게 가장 쉽고 익숙한 방법으로 출력했다.