[재귀함수]★★백준 1914번 하노이 with Python3

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

1914번: 하노이 탑

문제

 

내 풀이

def move(no: int, x: int, y: int) -> None:
    if no > 1:
        move(no-1, x, 6-x-y)

    print(f'{x} {y}')

    if no > 1:
        move(no-1, 6-x-y, y)


n = int(input())
a = 2**n - 1
print(a)

if n < 21:
    move(n, 1, 3)

해설

이해하지 못하고 답을 보고 구현만 했다...

정답 풀이를 봐보자.

 

정답 풀이

def f(n, a, b, c):
  if(n == 1):
    print(a, c, sep = " ")
  else:
    f(n-1, a, c, b)
    f(1, a, b, c)
    f(n-1, b, a, c)

n = int(input())
print(2**n-1)
if(n <= 20):
  f(n, 1, 2, 3)

출처:https://justicehui.github.io/ps/2019/05/06/BOJ1914/

 

해석

약 2^100을 구하는 코드를 C++로 작성하기 싫어서 python으로 풀었습니다.
먼저, 원판이 N개 있다면 이동 횟수는 항상 2N-1입니다.

1번 기둥에 N개의 원판이 있고, 3번 기둥으로 옮겨야 한다고 합시다.
N개의 원판을 모두 3번 기둥으로 옮기는 방법은 아래와 같습니다.

1. 1번 기둥에 위치한 N개의 원판 중, 위에 있는 N-1개의 원판을 2번 기둥으로 옮긴다.
2. 1번 기둥에 남아있는 1개의 원판을 3번 기둥으로 옮긴다.
3. 2번 기둥에 있는 N-1개의 원판을 3번 기둥으로 옮긴다.

이를 재귀함수로 구현해봅시다.

f(n, a, b, c) : n개의 원판이 a기둥에 있을 때, c기둥으로 모두 이동시키는 함수 로 정의합시다.
만약 n = 1이면 a에서 c로 하나 옮기고 끝내면 되겠죠.
나머지 경우를 살펴봅시다.

1. a번 기둥에 위치한 N개의 원판 중, N-1개를 b번 기둥으로 잠시 옮겨야 하니 f(n-1, a, c, b)를 호출합니다.
2. a번 기둥에 남아있는 1개의 원판을 c로 옮겨야 하니까 f(1, a, b, c)를 호출합니다.
3. b번 기둥에 잠시 놓았던 N-1개를 c번으로 옮겨야 하니까 f(n-1, b, a, c)를 호출합니다.

이렇게 3단계만 작성하면 됩니다.