[백준] 1914번 하노이 탑 (파이썬)

문제

1914번: 하노이 탑

 

코드

def hanoi(n, start, goal, side):
    # 1일 경우(가장 작다) 골로 보내줘
    if n == 1:
        return print(start, goal)
    
    # 아니라면 n-1하면주고 goal, side 위치를 바꿔줘
    # 짝 = goal, side 위치 변경
    hanoi(n-1, start, side, goal)
    
    # 재귀하고 나오면(작은 수가 빠졌다.) 움직일 수 있다
    # 1일 경우와 다른 축에 넣어줘야함
    print(start, goal)
    hanoi(n-1, side, goal, start)

n = int(input())
# 큰 수를 끝으로 옮기는 것 2**n 마지막 -1
# 20초과하는 수도 나와줘야함
print((2**n) - 1)

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

해설

처음에는 리스트로 풀수 있는 줄 알고 도전했으나, 풀지 못해서 해당 알고리즘을 찾아보고 나중에 다시 풀어보았다. 재귀함수를 많이 이해해야지 풀수있는 문제이다.

일단 이동 수는 2의 n승의 -1이다. 자세한 풀이 과정은 하노이의 탑을 검색해보면 이해하기 쉬울 것이다.

하노이 탑

 

우리가 주의해야 할 점은, goal에서는 판을 빼면 안되기 때문에 goal은 start 점에 있을 수 없는 것과 n == 1이라면 return하여 더 재귀하지 못 하게 해주는 점이다.

코드에서 보기 편하도록 enter를 넣어놨다. n ==1되기 전까지 1번 hanoi에서 재귀가 되고 n==1면 print하고 return하여 그 직전에 재귀로 돌아가서 다시 print를 해주게 하였다. 

재귀를 간단하게 표를 만들어보면 아래와 같다, 빨간 * bold는 print하는 것이고, n이 빨강이 아니라면 return하면서 print된 값이다.

n	start	goal	side
3	1	3	2
2	1	2	3
1	1	3	1
2	1	2	3
1	3	2	1
none	none	none	none
none	none	none	none
3	1	3	2
2	2	3	1
1	2	1	3