백준 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

 

풀이

유명하디 유명한 하노이 탑의 최소 이동횟수와 이동과정을 출력하는 문제이다.

 

이 문제는 재귀함수를 쓰면 꽤 쉽게 풀리는데, 높이가 n인 하노이 탑의 함수를 hanoi(n)이라고 하면, hanoi(n)은 hanoi(n-1) 2개와 print문 1개로 표현할 수 있다. 그 이유는 하노이 탑의 성질에 있다.

높이가 3인 하노이 탑을 예시로 들면,

1. 높이가 2인 탑을 여분의 장대로 옮긴다.
2. 넓이가 3인 원판을 목표로하는 장대로 옮긴다.
3. 여분의 장대에 있는 높이가 2인 탑을 목표로하는 장대로 옮긴다.

이 3개의 과정으로 나눌 수 있다. 여기서 과정1과 3은 높이가 2인 하노이 탑을 옮기는 것과 같고, 중간에 과정 2를 추가하면 되는 것이다. 여기서 과정 2는 print문으로 표현 할 수 있다.(시작장대에서 목표장대로)

하지만 과정 1의 입장과 과정 3의 입장을 비교해서 보면, 각각의 시작장대, 경유장대, 목표장대가 다르다. 이는 매개변수를 바꾸면 된다.

결론은 시작장대를 start, 목표장대를 to, 경유장대를 via라고 했을 때,

hanoi(n,start,to,via)는 hanoi(n-1,start,via,to), print(start,to), hanoi(n-1,via,to,start)의 과정을 거치면 되는 것이다.

또, 하노이의 최소 이동횟수는

n=1일때 1

n=2일때 3

n=3일때 7

n=4일때 15

n=5일때 31로, 2^n-1임을 알 수 있다.

 

코드

def hanoi(n,start,to,via):
    if n==1:
        print(start, to)
    else:
        hanoi(n-1,start,via,to) 
        print(start, to) 
        hanoi(n-1,via,to,start)
n = int(input())
print(2**n-1)
hanoi(n, 1, 3, 2)

n이 1일땐 그냥 이동하면 된다.(print문)

 

 

재귀함수를 맛깔나게 쓸 수 있는 예제였다고 생각한다. 풀면서 재미있었다.