[백준 파이썬] #11729 하노이 탑 이동 순서

Silver II

# 11729 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

 

구글링을 통해 답을 확인하고 해석하였다.

def hanoi_tower(n, start, by, end):
    if n == 1:
        print(start, end)
        return
    # 1개의 블럭일 때 start에서 end로 이동
    
    hanoi_tower(n-1, start, end, by) # n-1개의 블럭을 start에서 by로 이동 
    print(start, end) # 나머지 1개(가장 큰) 블럭을 start에서 end로 이동
    hanoi_tower(n-1, by, start, end) # by로 이동했떤 n-1개의 블럭을 end로 이동

n = int(input())
print(n**2-1)
hanoi_tower(n, 1, 2, 3)

• 하노이의 탑은 재귀함수로 풀이를 진행하는 것이 좋다
• n-1개를 적용했을 때 값이 n개를 적용한 값을 도출하는데 큰 역할을 하기 때문

 

 

[코드 구현 아이디어]

   1. n-1개를 보조 공간에 모두 이동시킨 후

 

   2. 가장 큰 덩어리를 목표 위치로 이동하고

 

   3. 보조 공간에 있는 n-1개를 목표 위치로 이동하는 방식

    

 

• 재귀함수로 풀이를 할 때 큰 덩어리부터 생각하도록 하자
• 처음 문제를 마주할 때 짝수, 홀수의 경우를 나누어 진행해야 하나 싶었다. 코드 구현에 따라 경우를 나누어 진행할 수도 있겠지만, 재귀함수로 풀이하는 거시적 관점과 다른 방향이라 어렵게 풀어내야 한다.
• 하노이의 탑 위치에 해당하는 '1, 2, 3'은 순서 정보를 갖지 않는다.
• 1, 2, 3이 순서대로라고 생각하면 오히려 코드 이해가 어렵다. 단지 공간1, 공간2, 공간3 정도로 보는 것이 좋으며, 이해가 되지 않는다면 순서 의미가 없는 빨강, 파랑, 초록 공간 정도로 생각하는 것이 도움이 될 것이다