[재귀] 11729번 하노이 탑 이동 순서

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분 + a

1. 문제 설명

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

11729번: 하노이 탑 이동 순서

2. 접근 방식

- 하노이 탑은 전형적인 재귀 문제로 보인다.

- 큰 문제를 작은 문제들로 계속해서 들어가서 하나씩 해결하면서 나오는 문제라고 생각하면 편할 듯 싶다. 

 [START]   [ASSIST]   [GOAL]

1. n-1개의 start 기둥에 있는 원반을 goal기둥을 이용해서 assist기둥에 놓는다.

2. n-1개 원반의 이동이 모두 끝나면, n번째 원반을 목표지점으로 옮긴다. 

3. n-1개의 assist 기둥에 있는 원반을 start기둥을 이용해서 goal기둥에 놓는다.

※ 여기서 n-1개의 원반을 재귀로 이동하는 이유는, n-1번째 원반은 n-2개의 원반들의 기준에서는 더 큰 원반이기 때문이다.

3. 코드

def hanoi(n, start, goal, assist):
    if n==1:
        ls.append((start, goal))
        return
    else:
	    # n-1개의 start 기둥에 있는 원반을 goal기둥을 이용해서 assist기둥에 놓는다.
        hanoi(n-1, start, assist, goal) 
        # n-1개 원반의 이동이 끝나면, n번째 원반을 목표지점으로 옮긴다. 
        ls.append((start, goal))
        # n-1개의 assist 기둥에 있는 원반을 start기둥을 이용해서 goal기둥에 놓는다.
        hanoi(n-1, assist, goal, start) 
        ls = []
n = int(input())
hanoi(n, 1, 3, 2)
print(len(ls))
for a, b in ls:
    print(a, b)

4. 코멘트

- 하노이탑 알고리즘의 경우 정해진 방법이 무조건 있는 알고리즘이다.
- 결국 하노이탑 문제의 알고리즘을 이해하고 있냐 못하냐의 싸움인 것 같다.
- 해당 알고리즘은 재귀를 이용한 대표적인 문제인 것 같다. 코드가 길지 않으니 외워두면 좋을 것 같다.