18_백준 _11729번 파이썬 하노이의 탑

악명 높은 하노이의 탑

문제예전에 풀어봐서

다시 복기하는 마음으로 코드를 짰다.

#재귀의 꽃#재귀함수의 스태디셀러 문제

 

• 풀이

x = int(input())
move = []
def move_disk(disk_num, start, end):
    move.append([start,end])
def hanoi(num_disks, start, end):
    if num_disks == 0:
        return
    else:
        other = 6 - start - end

        # 1. 가장 큰 원판을 제외하고 나머지 원판들을 start에서 other로 이동
        hanoi(num_disks - 1, start, other)

        # 2. 이동경로 저장 : 가장 큰 원판을 start에서 end로 이동
        move_disk(num_disks, start, end)

        # 3. 나머지 원판들을 other에서 end로 이동
        hanoi(num_disks - 1, other, end)


hanoi(x, 1, 3)
print(len(move))
for i in move:
    print(i[0],i[1])

# 입력 
3
# 출력
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3