[백준 11729] 하노이 탑 이동 순서(파이썬)

문제 출처 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

 

하노이 탑은 프랑스 수학자 에두아르 뤼카(Edouard Lucas)가 발표한 게임 입니다.

왼쪽의 읬는 원판을 오른쪽 원판으로 이동시켜야 합니다. 이 때 다음의 규칙이 적용되어야 합니다.

1. 한 번에 한 개의 원판만 이동할 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
3. 이동 횟수는 최소가 되어야 한다.

이 세가지 규칙을 지키면서 원판을 이동해야 합니다. 이렇게 이동하기 위해서는 두개의 원판이 가운데 와야 합니다.

왜냐하면 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 하기 때문 입니다. 위와 같은 모양이 되지 않는다면 왼쪽 가장 큰 원판을 오른쪽에 옮길 수 없기 때문 입니다.

이제 가장 큰 원판이 오른쪽으로 이동했기 때문에 가운데 있는 판들을 오른쪽으로 이동할 수 있습니다. 이 단계를 숫자를 써보면 아래와 같습니다.

• 3개의 원판을 1에서 3으로 옮기기
  • 2개의 원판을 1에서 2로 옮기기
    • 1개의 원판을 1에서 3으로 옮기기
    • 1개의 원판을 3에서 2로 옮기기
  • 2개의 원판을 2에서 3으로 옮기기
    • 1개의 원판을 2에서 1으로 옮기기
    • 1개의 원판을 1에서 3으로 옮기기

이렇게 과정이 반복되게 됩니다. N개의 원판을 1번위치에서 3번 위치로 이동시키는 하노이탑에 대한 함수를 아래와 같이 정의해 보겠습니다.

입력 받기

N = int(input())
hanoi(N, 1, 2, 3)

원판의 갯수 N을 입력 받았습니다. 그리고 하노이탑 함수를 만들었습니다. N은 원판의 갯수를 의미하고 1에 있는 N개의 원판을 2를 통해서 3으로 옮기겠다는 뜻 입니다. 1번 위치가 시작위치가 되고, 2번 위치가 보조를 하며, 3번 위치로 이동시키는 것입니다. 그것을 함수로 아래와 같이 표현 합니다.

재귀 함수 구현

# N개의 원판을 start위치에서 by를 보조로 end 위치로 이동 시키는 함수
def hanoi(n, start, by, end):
    hanoi(n-1, start, end, by)
    hanoi(n-1, by, start, end)

위에서 N개의 원판을 1번에서 3번으로 이동시키기 위해서 먼저 N-1개의 원판을 1번에서 2번으로 이동 시키고, 다음으로 2번에서 3번으로 이동시켜 주었습니다. 그것을 위와같이 표현한 것입니다. 이렇게만 하면 종료조건이 없기 때문에 끝없이 함수를 반복합니다. 따라서 우리는 종료조건을 넣어주어야 합니다.

종료 조건 추가

# N개의 원판을 start위치에서 by를 보조로 end 위치로 이동 시키는 함수
def hanoi(n, start, by, end):
    if n == 1: # 원판이 한개 남으면 끝냄
        return
    hanoi(n-1, start, end, by)
    hanoi(n-1, by, start, end)

이렇게 하면 원판이 한개 남았을 때 종료를 하게 됩니다. 정상적으로 종료가 되긴 하겠지만 아무 기록이 없기 때문에 확인할 방법이 없습니다.

원판의 이동 저장하기

이 문제에서는 원판이 이동하는 것을 확인해야 하기 때문에 원판의 이동에 대해 리스트에 넣어주어 보겠습니다.

ans = []
# N개의 원판을 start위치에서 by를 보조로 end 위치로 이동 시키는 함수
def hanoi(n, start, by, end):
    if n == 1: # 원판이 한개 남으면 끝냄
        ans.append((start, end))
        return
    hanoi(n-1, start, end, by)
    ans.append((start, end))
    hanoi(n-1, by, start, end)

원판이 이동할 때마다 시작과 끝의 위치를 저장해 놓습니다. 이렇게 저장이 된 리스트를 마지막에 횟수와 이동 경로를 출력해 주면 됩니다.

출력하기

print(len(ans))
for a in arr:
    print(*a)

재귀함수를 처음부터 완벽하게 이해할 수는 없습니다. 하나하나 따라하면서 재귀함수에 익숙해지면 함수가 어떻게 실행되는지 알 수 있게 됩니다. 조급한 마음을 가지지 말기를 바랍니다.

전체 코드

N = int(input())

ans = []
def hanoi(n, start, by, end):
    if n == 1:
        ans.append((start, end))
        return

    hanoi(n-1, start, end, by)
    ans.append((start, end))
    hanoi(n-1, by, start, end)

hanoi(N, 1, 2, 3)
print(len(ans))
for a in ans:
    print(*a)