[백준] 11729번 : 하노이 탑 이동 순서 Gold5(골드5) - JAVA[자바]

[Gold V] 하노이 탑 이동 순서 - 11729

문제 링크

성능 요약

메모리: 100692 KB, 시간: 416 ms

분류

재귀

제출 일자

2023년 11월 26일 12:12:23

문제 설명

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

 

1. 첫번째 기둥에 있는 원판들을 마지막 기둥에 꽂아 넣어야 함.

2. N번째 원판을 마지막 기둥에 꽂기 위해서는 1부터 N-1번째 원판까지를 중간 기둥에 옮겨야 한다.hanoi(N-1)번

3. N번째 원판을 마지막 기둥으로 옮긴다.(1번)

4. 중간 기둥에 꽂혀있는 1부터 N-1번째 원판들을 마지막 기둥에 옮긴다.hanoi(N-1)번

ex) N = 3일 때

1. 첫번째 기둥에 있는 {1,2,3} 원판들 중 3을 마지막 기둥으로 옮기기 위해서는 {1,2} 원판을 중간 기둥으로 옮겨야한다.- hanoi(3-1)

2. {1,2} 기둥을 중간 기둥으로 옮기기 위해서는 {1} 원판을 마지막 기둥으로 옮겨야한다. - (hanoi(2-1)

3. {2}기둥을 중간 기둥으로 옮긴다.( 1번 )

4. 마지막 기둥에 있는 {1} 원판을 두번째 기둥으로 옮긴다. - hanoi(2-1)

5. {3} 원판을 마지막 기둥으로 옮긴다.

6. 중간 기둥에 있는 {1,2} 원판을 마지막 기둥으로 옮긴다.

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

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

    private static void hanoi(int n, int start, int mid, int to){
        result++;
        if(n == 1){
            sb.append(start + " " + to).append("\n");
            return;
        }
        hanoi(n-1,start,to,mid);
        sb.append(start + " " + to).append("\n");
        hanoi(n-1,mid,start,to);
    }
}