• 문제: https://www.acmicpc.net/problem/1914

설명

재귀 문제에서 자주 볼 수 있는 하노이탑을 알아보자.

하노이탑 문제는 크게 3단계로 풀이할 수 있다.
1. 맨 밑에 판(빨)을 제외하고 두 판(파, 초)을 보조 장대로 이동한다.
2. 맨 밑에 있는 판(빨)을 도착 장대로 이동한다.
3. 보조 장대로 이동한 두 판(파, 초)을 도착 장대로 이동한다.

원판 움직이기

하나의 원판 움직이기

def hanoi(n, start, temp, end):	# n: 원판의 개수, start: 시작, temp: 보조, end: 도착
	if n == 1:
    	print(start, end)   

둘 이상의 원판 움직이기
빨간 원판 위의 두개 원판을 보조 장대(temp)로 이동시킨다. 이제 보조 장대가 도착 장대가 된다.

def hanoi(n, start, temp, end):	# n: 원판의 개수, start: 시작, temp: 보조, end: 도착
	if n == 1:
    	print(start, end)
	else:
    	hanoi(n-1, start, end, temp)	# 파라미터의 순서를 생각해라!
		print(start, end)

맨 밑에 있는 원판을 도착 장대로 이동시킨다.

보조 장대에 있는 남은 원판들을 도착 장대로 보낸다.
이제 보조 장대가 시작 장대가 되고, 시작 장대는 보조 장대가 된다.

def hanoi(n, start, temp, end):	# n: 원판의 개수, start: 시작, temp: 보조, end: 도착
	if n == 1:
    	print(start, end)
	else:
    	hanoi(n-1, start, end, temp)	# 파라미터의 순서를 생각해라!
		print(start, end)
        hanoi(n-1, temp, start, end)

총 움직임 계산하기

코드

from sys import stdin as s

n = int(s.readline())
def move(n, start, temp, end):
    if(n == 1):
        print(start, end)
        return

    # 처음 기둥에서 중간 기둥으로 옮긴다.
    move(n-1, start, end, temp)

    print(start, end)

    move(n-1, temp, start, end)

print(2**n - 1)

if(n <= 20):
    move(n, 1, 2, 3)

책에서는 start(1), end(2), temp(3)이라면 합이 어차피 6이니까 temp를 6-start-end 이렇게 표현하기도 하였다.

Reference

• https://velog.io/@jieuihong/%EB%B0%B1%EC%A4%80-11729-%ED%95%98%EB%85%B8%EC%9D%B4%ED%83%91