[백준] 11729번 하노이 탑 이동 순서 - JAVA

문제

 

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 큰 순서대로 쌓여 있다. 

 

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야한다.
3. 이동 순서는 최소가 되어야한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하라

 

 

 

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

11729번: 하노이 탑 이동 순서

 

 

 

 

 

 

입, 출력

 

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

 

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

두 번째 줄부터 수행과정을 출력한다.

 

// 입력
3

// 출력
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

 

 

 

 

 

 

풀이 (설명)

 

Tip) 풀이 코드는 아래에 있습니다.

 

최소 이동횟수

우리는 N개의 원판이 있으면 N-1개는  서브 장대에 옮길 것이고 맨아래에 있는 N번째 원판을 도착할라는 3번째 장대에 옮길 것이다.

그럼 N-1개의 원판은 서브 장대에 갔다가 도착지점인 3번째 장대에 옮겨 지므로 2(N-1) 번 실행 될것이고

N번째 원판은 3번째 장대에만 옮겨지면 되므로 +1 번 실행될 것입니다.

 

즉, 최소 횟수 = 2 × ( N-1 ) + 1 입니다.

 

아래와 같이 순서대로 확인해보면 

 

• 1개의 원판을 옮기는데 걸리는 횟수 = 1회
• 2개의 원판을 옮기는데 걸리는 횟수 = 2 * 1 + 1 = 3회
• 3개의 원판을 옮기는데 걸리는 횟수 = 2 * 3 + 1 = 7회
• 4개의 원판을 옮기는데 걸리는 횟수 = 2 * 7 + 1 = 15회

출처 : 네이버 지식백과

원판 옮기기

만약 원판이 1개 일 때의 조건을 먼저 걸어준다.

1개 밖에 없으면 start(=1번째 장대) 에서 destination(=3번째 장대) 로 바로 이동하면 되기 때문에 hanoi(1)이 된다.

 

이제 N개의 원판이 있을 때를 보자

STEP 1 : N-1개를 Start장대에서 Sub 장대로 이동

 

STEP 2 : 제일 큰 원판 (마지막 원판)을 Start장대에서 destination 장대로 이동

 

STEP 3 : sub 장대에 있는 N-1개 원판을 destination 장대로 이동

 

 

 

 

 

 

풀이 (코드)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        // 최소 이동 횟수
        int count = (int) Math.pow(2, N) -1;

        hanoi(N, 1, 2, 3);
        System.out.println(count);
        System.out.println(sb.toString());
    }

    /**
     *
     * @param N  원의 개수
     * @param start  시작 위치
     * @param sub   옮길 때 잠시 둘 서브 장대
     * @param destination   옮길 위치
     */
    public static void hanoi(int N, int start, int sub, int destination){

        if(N == 1){
        	// 원판이 하나일 때, 시작위치에서 옮길 위치로 1번에 옮기기
            sb.append(start).append(" ").append(destination).append("\n");
            return;
        }

        //  STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 sub 지점으로 옮긴다.)
        hanoi(N-1, start, destination, sub);

        // STEP 2 : 가장 큰 원판을 A에서 C로 이동 (= start 지점의 N번째 원판을 destination지점으로 옮긴다.)
        sb.append(start).append(" ").append(destination).append("\n");

        // STEP 3 : N-1개를 B에서 C로 이동 (= sub 지점의 N-1개의 원판을 destination 지점으로 옮긴다.)
        hanoi(N-1, sub, start, destination);

    }
}

 

 

 

감사합니다.