백준-11729-하노이 탑 이동 순서

하노이 탑 문제는 대표적인 재귀(분할정복) 문제이다.

문제

하노이 탑 이동 순서 (https://www.acmicpc.net/problem/11729)

풀이

1. 문제조건 해석

   일반적인 하노이 탑 문제이다.

2. 알고리즘

   • 재귀를 효율적으로 이용한다.

     1. 1위치의 n-1개 원반을 2로 보낸다.
     2. 1위치의 1개 원반을 3으로 보낸다.
     3. 2위치의 n-1개 원반을 3으로 보낸다.
   • from, by, to 와 같은 매개변수 전달에 유의
   • 총 이동 횟수는 $2^n-1$ (1<<n)-1 이다.

3. 코드

n = int(input())

move = []
cnt = 0
def hanoi(m, fro, by, to): # m개 원반을 fro에서 by를 거쳐 to로 보낸다.
    global cnt
    global move
    if m == 1:
        move.append([fro, to])
    else:
        # m-1 개 원반을 to를 거쳐 by로 옮긴다.
        hanoi(m-1, fro, to, by)
        # 1개 원반을 to로 옮긴다.
        move.append([fro ,to])
        # m-1개 by에 있는 원반을 fro 거쳐 to로 옮긴다.
        hanoi(m-1, by, fro, to)
    cnt += 1

hanoi(n, 1, 2, 3)
print(cnt)
for m in move:
    print(m[0], m[1])