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

접근법

---

재귀의 대표적인 문제 하노이 탑이다. 우선 아래 원판이 4개인 경우를 역순으로 진행해보자.

 

원판이 4개인 경우

먼저 4개의 원판을 전부 3위치에 옮겨 놓기 위해서는 아래처럼 2번 위치에 1번, 2번, 3번 원판이 위치해 있어야한다.

 

그래야 4번 원판을 3번 위치의 가장 아래에 놓을 수 있기 때문이다.

 

자 그럼 2번 위치에 1, 2, 3 원판이 위치하기 위해서는 1, 2번 원판은 3번에 있어야 한다.

 

그래야 3번 원판을 2번 위치에 놓을 수 있기 때문이다.

 

 

또한 마찬가지로 1, 2번 원판이 3번 위치에 있기 위해서는 1번 원판을 우선 2번 위치에 두어야 한다.

 

그래야 2번 원판을 3번 위치에 놓을 수 있기 때문이다.

 

 

쉽게 일반화 해보자. 가장 먼저 해야할 일은 원판의 갯수 n개가 주어졌을 때,

 

Step 1 : n-1개의 원반을 2번 위치로 옮겨야 하고

 

Step 2 : 가장 큰 원반 1개를 1번 위치에서 3번 위치로 옮긴 뒤에

 

Step 3 : n-1개의 원반을 2번 위치에서 3번 위치로 옮겨야 한다.

 

즉 ! 원반 n개를 이동하는 것은 n-1개의 원반을 이동하는 문제가 되는 것이고 이것은 결국 원반 1개를 이동하는 문제로

 

세분화 되는 것이다.

 

따라서 위의 개념을 바탕으로 간단하게 코드로 살펴보면,

 

 

def function(N, From, By, To):
	# 이동할 원반의 수가 1개인 경우
    if N == 1:
    	print('원반을 그냥 From에서 To로 이동')
    
    else :
    	# Step 1 
        function(N-1 개를 1번 위치에서 2번 위치로 이동)
        
        # Step 2
        print('가장 큰 원반 N을 From 에서 To로 이동')
        
        # Step 3
        function(N-1 개를 2번 위치에서 3번 위치로 이동)

 

 

풀이

---

def hanoi(N, From, By, To):
    
    if N == 1:
        step.append([From,To])
    else :
        hanoi(N-1, From, To, By)
        step.append([From,To])
        hanoi(N-1, By, From, To)
        
step = []
n = int(input())
hanoi(n,1,2,3)

print(len(step))
print('\n'.join(([' '.join(str(element) for element in row) for row in step])))

 

@ 문제 출처 : 백준