[BOJ] 11729 - 하노이 탑 이동 순서 JAVA

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

문제

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

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

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

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

입력

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

 

출력

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

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

예제 입력 1

3

예제 출력 1

7

1 3

1 2

3 2

1 3

2 1

2 3

1 3

 

 

 

 

 

 

 

풀이 .

import java.io.*;

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static int cnt;

    public static void hanoi(int n, int from, int to, int temp) {
        if(n == 1) {
            sb.append(from + " " + to + "\n");
            cnt += 1;
        }else {
            hanoi(n-1, from, temp, to);
            sb.append(from + " " + to + "\n");
            cnt += 1;
            hanoi(n-1, temp, to, from);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        hanoi(n, 1, 3, 2);

        System.out.println(cnt);
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

 

재귀에 대한 통찰을 키울 수 있었던 문제.

 

 

N개의 원판을 장대1에서 장대3으로 옮기는 방법

1. N-1개의 원판을 2로 옮긴다.

2. N개중 가장 큰(맨 밑에 있던) 원판을 3으로 옮긴다.

3. 2에 있던 N-1개의 원판을 3으로 옮긴다.

(N-1개를 옮기는 과정에서는 N-2가, N-2개를 옮기는 과정에서는 N-3이 ... 이런식으로 재귀가 발생한다)

 

위 과정을 수행할 때 3개의 장대는 필연적으로 모두 사용되어진다.

이 셋을 각각 from, to, temp (출발지, 도착지, 경유지)로 구분하였다.

 

당연한 말이지만 3개의 장대 중에서 from, to를 제외한 나머지 하나가 temp가 된다.

 

처음에는 temp가 굳이 필요할까 라는 생각을 했지만 반드시 필요하다.

재귀가 이뤄지는 과정에서 from, to가 temp가 되어 들어가기도 하고 temp가 from, to가 되어 들어가기도 하기 때문에 반드시 temp가 필요하다.

 

하노이 탑의 시간 복잡도는 O(2^N)이다.

2^N - 1번의 연산으로 N개의 원판을 모두 옮길 수 있다.

 

 

 

아래 블로그의 글에서 큰 도움을 얻었다.

shoark7.github.io/programming/algorithm/tower-of-hanoi