[백준(BOJ)] #1914- 하노이 탑 (파이썬, PyPy3)

문제

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

1914번: 하노이 탑

---

문제 풀이

재귀 알고리즘 적용

2022.07.05 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

[파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

 

첫 번째 장대에서 세 번째 장대로 3(n) 개의 원판을 옮기는 과정

 

1)

 

2)

 

3)

 

4)

 

5)

 

6)

 

7)

 

- n-1개의 원판을 두 번째 장대에 놓는다. 1) ~ 3)
- 1 개의 원판을 세 번째 장대에 놓는다. 4) 
- 두 번째 장대에 있는 n-1개의 원판을 세 번째 장대에 놓는다. 5) ~ 7)

 

이를 구현하기 위해 재귀 알고리즘을 사용하여 다음과 같이 코드를 작성할 수 있습니다.

# 재귀 알고리즘
# a 장대에서 b 장대로 k-1개를 놓음
dfs(a, c, b, k-1)
# a 장대에서 c 장대로 제일 큰 원판을 놓음
dfs(a, b, c, 1)
# b 장대에서 c 장대로 나머지 k-1개를 놓음
dfs(b, a, c, k-1)

---

구현

코드

import sys
input = sys.stdin.readline

def dfs(a, b, c, k):
    if k == 1:
        print(a, c)
        return
    dfs(a, c, b, k-1)
    dfs(a, b, c, 1)
    dfs(b, a, c, k-1)

if __name__ == "__main__":
    n = int(input())

    print(2 ** n - 1)
    if n <= 20:
        dfs(1, 2, 3, n)

결과