[백준]11729. 하노이 탑 이동 순서 문제풀이 (파이썬, python)

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

위 문제는 문제의 제목과 같이, 하노이 탑의 이동 순서를 표현하는 문제이다.

 

우선 기본적인 하노이 탑의 규칙은 다음과 같다.

1. 세개의 막대가 있고, 첫 번째 막대에는 반지름이 각자 다른 N개의 원판이 있다.

2. 원판은 반지름의 크기가 큰 순서로 이루어져 있다.

3-1. 이때, 한 번에 한개의 원판만 이동 할 수 있다.

3-2. 쌓인 원판은 위의 것이 항상 아랫 것보다 작아야 한다.

4. 이 두 가지 원칙을 지키면서 모든 원판을 세 번째로 이동시켜야 한다.

 

문제가 요구하는 점을 요약해 보면, 

1. 원판의 개수 N을 입력 받는다

2. 하노이판 규칙에 따라 원판을 옮기는 횟수 K를 출력한다.

3. 두 번째 줄부터 K 번째 줄까지 A번째 탑 맨 위의 원판을 B번째 탑으로 옮긴다는 의미의 A B를 공백을 두고 출력한다.

 

처음에 문제를 보고 고민을 많이 하였다.

 

1. 어떤 방식으로 해결할 것인가?

 우선 문제를 보았을 때, 우리가 하노이 탑을 해결하는 해결법에 대해 우선 생각을 해보았다. 평상시에 하노이 탑을 할 경우, 첫 번째 막대에 4개의 원판이 있다고 가정하고, 원판은 크기가 작은 순서대로 A, B, C, D라고 해보자.

 

이때, 원판 모두 세 번째 막대에 옮기기 위해서는,

1. A를 2번째 막대로 옮긴다.

2. A,B를 3번째 막대로 옮긴다.

3. A,B,C를 2번째 막대로 옮긴다.

4. A,B,C,D를 3번째 막대로 옮긴다.

보통 일련의 과정을 거치게 된다.

 

 이를 통해서, n개의 원판을 지닌 하노이탑을 해결하기 위해서는 n-1, n-2, n-3, ..., 1개의 원판을 다른 쪽 막대로 이동시켜야 한다는 사실을 알 수 있습니다.

 따라서, 일단 재귀를 활용해야 한다는 사실을 확인 할 수 있습니다.

-> 재귀 활용하기

 

2. 재귀 함수를 어떤 식으로 사용해야 할 것인가?

 앞의 과정에서 함수의 파라미터가 무엇이 필요한지를 우선 확인할 수 있다. 예시의 일련의 과정들을 보면, 총 4가지의 파라미터가 필요하다.

1. 움직이고자 하는 원판의 총 개수, 2. 출발하는 막대, 3. 도착하는 막대, 4. 경유하는 막대

 

 또한, 우리가 하노이 탑을 하는 과정을 생각해 보면, 함수의 형태를 확정지어 볼 수 있다. 하노이 탑 함수를 Hanoi()라고 하고, 위의 파라미터를 받는다고 하였을 때

 

Hanoi(4, 1, 3, 2) # 원판의 개수는 4개, 1번째 막대에서 4번째 막대로 를 해결하려면

 

1. Hanoi(3, 1, 2, 3)

- 원판의 개수가 4개인 하노이탑을 해결하려면 우선 그보다 1 낮은 3개의 원판들을 2번 막대에 움직여야, 마지막 4번째 원판을 3번째 막대에 놓을 수 가 있다.

 

2. 1번째 막대에 있는 4번째 원판을 3번째 막대로 이동

 

3. Hanoi(3, 2, 3, 1)

- 4번째 원판을 이동시킨 후, 기존에 움직였던 3개의 원판들을 다시 3번째 막대로 옮긴다.

 

이를 일반화 시키면,

Hanoi(n, start, end, to) 를 입력 받았을시

n이 1이 아니면

1. Hanoi(n-1, start, to, end)

2. print(start, end)

3. Hanoi(n-1, to, end, start)

n이 1이라면 

1. print(start, end)

 

따라서 코드를 작성해 보면

def hanoi(max: int, start: int, end: int, to: int):
    if max == 1:
        print(start, end) # 가장 큰 하노이판 옮기기
    else:
        hanoi(max-1, start, to, end)
        print(start, end)
        hanoi(max-1, to, end, start)
if __name__ == "__main__":
    n = int(input())
    print(2**n-1)
    hanoi(n, 1, 3, 2)