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

#이 문제는 풀지 못했다.. 심지어 이해하기도 힘들었다. 나같은 사람을 위해 코드를 해체해봤다.

문제

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

정답 코드

def hanoi(n, a, b):
    if n > 1:									[과정A]
        hanoi(n-1, a, 6-a-b)              
                                          
    print(a, b)									[과정C]

    if n > 1: 									[과정B]
        hanoi(n-1, 6-a-b, b)

n = int(input())

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

 

풀이

n=3 일 때,

CODE의 맨 마지막 줄에 있는 hanoi(n,1,3)은 3개의 원반이 있을 때, 기둥1에서 기둥3으로 이동하는 것을 의미한다.

 

먼저 hanoi(3,1,3)으로 시작한다.

 

3개의 원반이 기둥1에서 기둥3으로 이동했다.

CODE의 [과정A]에 따르면 hanoi(2,1,2)가 되고, [과정C]에 따르면 print(1,3)가 된다. [과정B]에 따르면 hanoi(2,2,3)이 된다.

 

1. hanoi(2,1,2): 2개의 원반을 기둥1에서 기둥2로 옮긴다.

 

>>hanoi(2,1,2)는 [과정A]에 따르면 hanoi(1,1,3)이 되고, [과정C]에 따르면 print(1,2)이 된다. [과정B]에 따르면 hanoi(1,3,2)가 된다.

 

1) hanoi(1,1,3): 1개의 원반을 기둥1에서 기둥3으로 옮긴다. 1번째 출력: print(1,3) 

 

2) print(1,2): 1개의 원반을 기둥1에서 기둥2로 옮긴다. 2번째 출력: print(1,2) 

 

3) hanoi(1,3,2): 1개의 원반을 기둥3에서 기둥2로 옮긴다. 3번째 출력: print(3,2) 

 

최종적으로 hanoi(2,1,2) 결과, 2개의 원반이 기둥1에서 기둥2로 옮겨졌다.

 

2. print(1,3): 나머지 1개의 원반을 기둥1에서 기둥3으로 옮긴다. 4번째 출력: print(1,3)

 

 

3. hanoi(2,2,3): 2개의 원반을 기둥2에서 기둥3으로 옮긴다.

 

>>hanoi(2,2,3)는 [과정A]에 따르면 hanoi(1,2,1)이 되고, [과정C]에 따르면 print(2,3)이 된다. [과정B]에 따르면 hanoi(1,1,3)이 된다.

 

1) hanoi(1,2,1): 1개의 원반을 기둥2에서 기둥1로 옮긴다. 5번째 출력: print(2,1) 

 

2) print(2,3): 1개의 원반을 기둥2에서 기둥3로 옮긴다. 6번째 출력: print(2,3) 

 

3) hanoi(1,1,3): 1개의 원반을 기둥1에서 기둥3로 옮긴다. 7번째 출력: print(1,3)