[BOJ] 백준 1914 하노이탑 - Python/Java

https://www.acmicpc.net/problem/1914

1914번: 하노이 탑

해설

이 문제가 실버2인 이유는 아마 대중적으로 알려진 문제라서 그렇지 않을까 생각합니다. 혼자서 풀려고 했을 때는 정말 모르겠어서 다른 사람들의 풀이를 참고해서 이해할 수밖에 없었습니다...☹️

 

하노이탑 문제의 핵심 아이디어는 원반 N개 문제를 해결하기 위해서는 원반이 N-1개인 문제를 해결하면 된다는 것인데요. 구체적으로 풀어서 이야기해보면 아래와 같습니다.

 

1) N개의 원반이 주어지면 위에서부터 N-1개의 원반을 두 번째 기둥으로 옮깁니다.

2) 그러면 현재 상태에서 첫번째 기둥에는 가장 큰 원반이 남아있고, 두 번째 기둥에는 N-1개의 원반이 남아있게 됩니다.

3) 그러면 첫 번째 기둥에 있는 원반을 세번째 기둥(목표 기둥)으로 옮기고 나면 이 문제는 N-1개의 원반을 다시 목표 기둥에 옮기는 문제가 됩니다.

 

이를 재귀적 코드로 작성하면 풀이는 아래와 같습니다.

 

[풀이 - 파이썬]

def hanoiTop_print(first, second, third, count):
    if count == 1:
        print(first, third)
        return
    
    # 원판 n-1개를 두 번째 기둥으로 옮기기
    hanoiTop_print(first, third, second, count-1)
    print(first,third)

    # 두 번째 기둥에 있는 원판을 마지막 기둥으로 옮기기
    hanoiTop_print(second, first, third, count-1)

n = int(input())
# 하노이탑을 완성하는 데 드는 횟수
print(2 ** n - 1)

# n이 20 이하일 때만 과정 출력
if n <= 20:
    hanoiTop_print(1, 2, 3, n)

 

[풀이 - 자바]

package PS;

import java.math.BigInteger;
import java.util.Scanner;

public class B_1914 {
    static int n;
    static void hanoiTop_print(int first, int second, int third, int count){
        if (count == 1){
            System.out.println(first + " " + third);
            return;
        }
        // 원판 n-1개를 두 번째 기둥으로 옮기기
        hanoiTop_print(first, third, second, count-1);
        System.out.println(first + " " + third);

        // 두 번째 기둥에 있는 원판을 마지막 기둥으로 옮기기
        hanoiTop_print(second, first, third, count-1);
    }
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        // 하노이탑을 완성하는 데 드는 횟수 출력
        System.out.println(BigInteger.valueOf(2).pow(n).subtract(BigInteger.ONE));
        if (n <= 20) hanoiTop_print(1,2,3,n);
    }
}