[JAVA] 백준 1914번 하노이 탑

문제

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

이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

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

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

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

 

 

입력

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

 

출력

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

N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

 

풀이

세 개의 장대가 있을 때, 2개의 원반을 1번 장대에서 3번 장대로 옮기는 경우는 아래와 같다.

 

1. 1번 원반을 중간 장대로 옮긴다.

2. 2번 원반을 목표 장대로 옮긴다.

3. 1번 원반을 중간 장대에서 목표 장대로 옮긴다.

 

세 개의 장대가 있을 때, 3개의 원반을 1번 장대에서 3번 장대로 옮기는 경우는 아래와 같다.

1번 원반과 2번 원반을 그룹화해서 생각하면 위와 같은 방법으로 진행이 된다.

 

1. 1번, 2번 원반을 중간 장대(mid)로 옮긴다.

2. 3번 원반을 목표 장대(end)로 옮긴다.

3. 1번, 2번 원반을 중간 장대(mid)에서 목표 장대(end)로 옮긴다.

 

위의 1번 과정을 진행할 때는 아까 본 것과 같다.

그러나 이젠 목표 장대가 mid이고, 중간 장대가 end가 된다.

 

1. 1번 원반을 중간 장대(end)로 옮긴다.

2. 2번 원반을 목표 장대(mid)로 옮긴다.

3. 1번 원반을 중간 장대(end)에서 목표 장대(mid)로 옮긴다.

 

위의 3번 과정도 똑같이 진행된다. 이제는 목표 장대가 end이고, 중간 장대가 start가 된다. 

 

1. 1번 원반을 중간 장대(start)로 옮긴다.

2. 2번 원반을 목표 장대(end)로 옮긴다.

3. 1번 원반을 중간 장대(start)에서 목적 장대(end)로 옮긴다.

 

원반을 출발 장대에서 목표 장대로 옮기는 것을 일반화 하면 아래와 같다.

 

1. 마지막 원반을 제외한 원반을 중간 장대로 옮긴다.
2. 마지막 원반을 목표 장대로 옮긴다.
3. 나머지 원반을 중간 장대에서 목표 장대로 옮긴다.

 

이를 간단하게 의사 코드로 작성하면 아래 처럼 된다.

 

hanoi(옮길 원반의 개수, 출발 장대, 목표 장대) {
	if 만약 옮길 원반이 0개면:
    		return
	마지막 원반을 제외한 나머지 원반 N-1개를 출발 장대에서 중간 장대로 옮긴다.
  	마지막 원반을 출발 장대에서 목표 장대로 옮긴다.
  	나머지 원반 N-1개를 중간 장대에서 목표 장대로 옮긴다.
}

 

이를 풀어서 작성하면 아래와 같다.

 

hanoi(옮길 원반의 개수, 출발 장대, 목표 장대) {
	if 만약 옮길 원반이 0개면:
    		return
 	hanoi(N-1, 출발 장대, 중간 장대)
   	print(원반 N을 출발 장대에서 목표 장대로 옮김!)
  	hanoi(N-1, 중간 장대, 목표 장대)
}

 

위의 코드를 바탕으로 코드를 작성하면 된다.

 

유의 사항

• 중간 장대를 파라미터로 넣어도 되지만 장대가 총 3개이므로, 출발 장대와 목적 장대가 있으면 중간 장대는 6 - 출발 장대 - 목표 장대로 구할 수 있다. (ex) 출발 장대: 1, 목표 장대 :3 , 중간장대 : 6-1-3= 2)
• N이 20보다 큰 경우에는 과정은 출력할 필요가 없으므로, 함수를 호출해 실제로 count하지 않고 공식을 써서 구해준다. 
• N = 100인 경우, 2의 100승을 계산해야 하므로 BigInteger를 사용해서 계산한다. (쓰지 않으면 메모리 초과됨)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    static StringBuilder sb = new StringBuilder("");
    static void hanoi(int n, int start, int end){
        if (n == 0)
            return;
        hanoi(n-1, start, 6 - start - end);
        sb.append(start);
        sb.append(" ");
        sb.append(end);
        sb.append("\n");
        hanoi(n-1, 6 - start - end, end);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        BigInteger num = new BigInteger("2");
        sb.append(num.pow(N).subtract(new BigInteger("1")));
        if (N <= 20){
            sb.append("\n");
            hanoi(N,1,3);
        } 
        System.out.println(sb);
    }
}

 

결과

 

문제	결과	메모리	시간	언어	코드 길이
1914	맞았습니다!!	37420 KB	448 ms	Java 11	908 B