[백준] 하노이 탑 이동 순서 - Java

문제 출처

https://www.acmicpc.net/problem/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

풀이 방법

• 스택, 재귀를 사용해 풀이하였다. 3개의 스택을 이용해, 1번 스택부터 숫자를 뽑아 2번에 두고 재귀를 통해 반복하면서 풀이하였다.
  • 이동한 좌표 (1 -> 3 등...)는 list에 저장해서, 마지막에 sb를 통해 한번에 출력해준다. 하나하나 sysout을 써버리면, 출력량이 미치도록 나오기 때문에 시간초과가 발생한다.

풀이 코드

package javalang;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 하노이탑이동순서_11729 {
    static int N, K;
    static Stack<Integer> one, two, three;
    static List<int[]> answer;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        one = new Stack<>();
        two = new Stack<>();
        three = new Stack<>();
        answer = new ArrayList<>();

        //LIFO이므로, 마지막 원소부터 추가한다.
        for(int i = N; i >= 1; i--){
            one.push(i);
        }

        hanoiTop();
    }

    public static void hanoiTop() {
        hanoi(N, one, three, two, 1, 3); 
        K = answer.size();    
        System.out.println(K);
        for (int[] move : answer) {
            sb.append(move[0]).append(" ").append(move[1]).append("\n");
        }
        System.out.print(sb);
    }
    
    public static void hanoi(int n, Stack<Integer> from, Stack<Integer> to, Stack<Integer> aux, int fromNum, int toNum) {
        if (n == 1) {
            int disk = from.pop();
            to.push(disk);
            answer.add(new int[]{fromNum, toNum});
            return;
        }
    
        hanoi(n - 1, from, aux, to, fromNum, 6 - fromNum - toNum);
        int disk = from.pop();
        to.push(disk);
        answer.add(new int[]{fromNum, toNum});
        hanoi(n - 1, aux, to, from, 6 - fromNum - toNum, toNum);
    }
}

• 여기서, 1 + 2 + 3 = 6이기 때문에 이동하는 번호는 6 - from - to 를 이용하여 적용시켰다.

결과

회고

• 재귀는 적으면서 해도 머리가 어지러운...