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

• 내가 이해한 하노이 탑의 원리는 a, b, c라는 세 개의 기둥이 존재할 때 a라는 기둥에서 c라는 기둥으로 n개의 원판을 옮기기 위해서는 a와 c가 아닌 b기둥에 n-1개의 원판을 옮겨둔 뒤 a에서 c로 n번째 원판(가장 밑에 있는 원판)을 옮기고 b에서 c로 n-1개의 원판을 옮겨주면 됩니다.
• 따라서 남는기둥에 n-1개의 원판을 옮겨둔 뒤 가장 큰 원판을 옮기고 n-1개의 원판을 옮겨주면 될 것입니다.
• 물론 이 과정에서 n-1개의 원판이 1개가 아닌 이상 위의 과정을 반복해야 합니다. 
• n-1개의 원판을 옮기기 위해서는 n-2개의 원판을 남는 기둥에 옮겨놓고 n-1번째 원판을 옮긴 뒤 n-2개의 원판을 옮겨주면 됩니다.

log = []


def hanoiTower(n, a, b, c):

    if n == 1:
        log.append([a, c])
        return
    else:
        hanoiTower(n-1, a, c, b)    # n-1개의 원판을 2번으로 옮기기
        log.append([a, c])          # 가장 큰 원판을 1번에서 3번으로 옮기기
        hanoiTower(n-1, b, a, c)    # 2번에 있는 n-1개의 원판을 3번으로 옮기기


hanoiTower(int(input()), 1, 2, 3)

print(len(log))

for _ in log:
    print(_[0], _[1])

• 코드를 살펴보자면 이동한 로그를 찍기위한 log리스트를 만들고 재귀 함수 hanoiTower를 생성했습니다.
• hanoiTower의 매개변수는 원판의 개수인 n과 기둥의 번호인 a, b, c를 할당했습니다.
• 원판이 1개일 때는 원판이 바로 1번에서 3번으로 이동하기 때문에 조건문으로 로그를 남겨주고 바로 값을 반환하여 재귀를 끊었습니다.
• 그리고 n-1개의 원판을 시작과 목표가 아닌 남는 기둥으로 옮긴 뒤, 가장 큰 원판을 시작 기둥에서 목표 기둥으로 옮겨주는 로그를 찍고 남아있는 n-1개의 원판들을 남는 기둥에서 목표 기둥으로 옮겨줍니다.
  • a에서 c기둥으로 옮길 예정이라며 a는 시작기둥, b는 남는 기둥, c는 목표 기둥입니다. 
  • 마찬가지로 b에서 c로 옮길 예정이라면 a는 남는 기둥이 됩니다.
  • 재귀를 사용하는 이유는 a에서 c로 n개의 원판을 옮기려 n-1개의 원판을 b로 옮기려면 n-1번째 원판을 옮기기 위해 n-2개의 원판을 c로 옮겨둬야 하기 때문입니다.
  • 그렇기 때문에 위의 재귀 함수를 통해 남는기둥과 목표 기둥, 시작 기둥을 설정하여 재귀 함수를 실행하면 그에 맞게 로그가 찍힙니다.