[백준 11729번-파이썬/Python] 하노이의 탑 이동 순서

http://acmicpc.net/problem/11729

{코드}

x = int(input())
print(2**x-1)
def hanoi(n, p1, p2, p3):
	if n == 1:
		print(p1, p3)
	else:
		hanoi(n-1, p1, p3, p2)
		print(p1, p3)
		hanoi(n-1, p2, p1, p3)
hanoi(x, 1, 2, 3)

{설명}

이 문제는 파이썬 클래스님의 하노이의 탑 알고리즘 영상과 JW MATHIDEA님의 하노이의 탑 일반항 포스트(왜 총 이동 횟수가 2**x+1인지)를 참고하시기 바랍니다.

간단하게 설명하자면 하노이의 탑 문제는 각 원반이 일정한 규칙에 따라 움직이며 n은 n번 원반이며 p1은 현재 기둥, p2는 보조 기둥, p3는 이동할 기둥입니다.

그리고 이 문제는 의미상으로 이동한다고 볼 수 있는데 else에서 n-1개의 원반을 보조 기둥으로 옮기면 현재 기둥에는 가장 큰 원반이 남아있으므로 최종 기둥으로 가장 큰 원반을 옮기고 보조 기둥에서 n-1개의 원반을 마지막 기둥으로 옮기는 작업을 하는 것입니다.

처음에 공부할 때는 배열을 써서 직접 움직여야 하나 싶었는데 하노이의 탑 규칙을 이해한 다음에 어떤 작업이 반복되는지 문제를 반복 작업(?)으로 바꾸는 방법을 공부해야 한다는 것을 이 문제를 통해 깨달았습니다.