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

문제

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

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

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

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

 

입력

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

 

출력

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

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

---

접근

분할과 정복이라는 알고리즘을 이해하기위해 해당 문제를 풀었다.

분할과 정복은 큰 문제를(여기서 큰 문제라는 것을 정확히 어떤 것을 의미하는지 파악할 필요가 있다.) 작은 단위의 문제로 나눠서 풀고 그것을 합쳐서 처음의 큰 문제의 해를 도출하는 것이다. 

아직까지 분할과 정복 알고리즘을 깊게 이해하지 못했다.

 

분할과 정복을 해당 문제에 적용을 해보자.

먼저 이 문제는 N개의 원판을 1번에서 3번으로 옮기는 것이다. 여기서 최종적으로 구해야하는 큰 문제가 이것이다. 이 문제를 작은 단위의 문제로 나눠서 풀면 편할까? 

1번에서 3번으로 이동하는 과정을 보면 먼저 N-1개의 원판을 1번에서 2번으로 이동하고, N번째에 있던 원판을 1번에서 3번으로 이동해야한다. 그리고 2번으로 이동했던 N-1개의 원판을 3번으로 이동시킨다.

 

따라서 이 문제는 3개의 문제로 나눠서 풀 수 있을 것이다.

1. N-1개의 원판을 1번에서 2번으로 이동시키기

2. N번째에 있던 가장 큰 원판을 1번에서 3번으로 이동시키기

3. 2번에 있는 N-1개의 원판을 3번으로 이동시키기

 

위에서 3개로 나눈 문제를 재귀로 해결을 해보자.

원판을 하나씩 줄여서 이동시켜본다면 결국 1번 원판을 먼저 이동시키게 되어있다. 1번 원판을 어딘가로 이동시키고 RETURN을 한다면 2번 원판을 어딘가로 이동시키면서 재귀호출을 풀어지게 될 것이다.

 

(아직 완벽하게 이해한 것같지 않고 나중에 다시 확실히 정리를 해야겠다.)

 

구현

옮길 원판의 개수 N을 입력받는다.

또한 최소 이동횟수는 2^N -1이 된다고 한다.

그리고 hanoi라는 함수를 통해 이동정보를 출력하게 되며 최종적으로 N개의 원판을 1번에서 3번으로 이동시키켜야하기 때문에 함수의 인자에 아래와 같이 전달하였다.

N = int(input())
print(2**N-1)
hanoi(N, 1, 3)

 

원판을 이동시키기 위해서는 N-1개의 원판을 1번에서 2번으로 먼저 이동시킨다. 이를 #1로 표현을 하였다. 이후 모두 이동시켰다면 N번째에 있던 원판을 1번에서 3번으로 이동시킨다. 마지막으로 2번으로 이동시켰던 것을 3번으로 이동시키는 것을 #3에 표현하였다.

def hanoi(n, start, end):
    if n == 1:
        print(start, end)
        return
	# 1
    hanoi(n-1, start, 6-start-end)
    # 2
    print(start, end)
    # 3
    hanoi(n-1, 6-start-end, end)

---

전체 코드

def hanoi(n, start, end):
    if n == 1:
        print(start, end)
        return

    hanoi(n-1, start, 6-start-end)
    print(start, end)
    hanoi(n-1, 6-start-end, end)

N = int(input())
print(2**N-1)
hanoi(N, 1, 3)