[Python] 백준 11729 하노이 탑 이동 순서

문제 바로가기

   문제분석   

# 한 번에 한 개의 원판만 이동 가능
# 쌓아 놓은 원판은 항상 위의 것이 아래것보다 작아야 함
# 이 작업을 수행하는데 필요한 이동순서 출력 프로그램 작성. 단 이동횟수는 최소
# 입력값은 첫번째 장대에 쌓인 원판의 개수 n으로 주어짐 (1 <= n <= 20)

# 기본적인 로직은

• 제일 바닥에 있는 원반을 뺀 나머지는 그룹으로 묶어 중간으로 보내고,
• 바닥을 목표로 보내고,
• 중간에 있던 그룹을 목표로 보낸다.

 

 

 

   문제풀이   

n = int(input())

def hanoi(n, a, b):
    if n > 1:
        hanoi(n-1, a, 6-a-b) 
    print(a,b)  
    
    if n > 1:         
        hanoi(n-1, 6-a-b, b)

print(2 ** n-1)
hanoi(n, 1, 3)

# 원반의 갯수를 입력값으로 받는다.

# 기둥이 1개 이상이면 그룹으로 묶인 n-1개 원판을 중간으로 먼저 다 옮긴다.

# n번째 원반이 a에서 b로 옮겨진다.

# 기둥이 1개 이상이면 남은 기둥 n-1개를 중간에서 b로 옮긴다.

# 총 이동해야하는 횟수를 출력하고

# 원판을 이동시키는 함수를 호출한다.(3개의 원판을 기둥 1에서 3으로 옮긴다)

 

 

참고자료: https://www.youtube.com/watch?v=qLJ3kHIuOKY