[백준] 1914번 하노이 탑

💡문제접근

• 재귀 알고리즘으로 해결할 수 있는 대표적인 문제인 하노이의 탑 문제다.

📌하노이의 탑

• 쌓아 놓은 원반을 최소 횟수로 옮기는 알고리즘
• 하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제
• 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작
• 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮겨야 한다.
• 이 때, 원반은 1개씩만 옮길 수 있으며 큰 원반은 작은 원반위에 쌓을 수 없다.

---

• ⅰ) 원반의 개수가 2개일 때 → 횟수 : 3
  ①. 그룹(원반1)을 시작 기둥 → 중간 기둥
  ②. 원반2를 시작 기둥 → 목표 기둥
  ③. 그룹(원반1)을 중간 기둥 → 목표 기둥

• ⅱ) 원반의 개수가 3개일 때 → 횟수 : 7
  ①. 그룹(원반1, 원반2)을 시작 기둥 → 중간 기둥
  ②. 원반3을 시작 기둥 → 목표 기둥
  ③. 그룹(원반1, 원반2)을 중간 기둥 → 목표 기둥

• ⅲ) 원반의 개수가 4개일 때 → 횟수 : 15
  ①. 그룹(원반1, 원반2, 원반3)을 시작 기둥 → 중간 기둥
  ②. 원반4를 시작 기둥 → 목표 기둥
  ③. 그룹(원반1, 원반2, 원반3)을 중간 기둥 → 목표 기둥

💡코드(메모리 : 31256KB, 시간 : 908ms)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N = int(input())

# start : 시작기둥, end : 끝기둥
def recursive(N, start, end):
	# N이 20보다 큰 경우 출력할 필요가 없다고 했으므로
    if N > 20:
        return

    if N == 1:
        print(start, end)
    else:
    	# 그룹(원반 N-1개)을 중간 기둥으로 이동 
        recursive(N-1, start, 6-start-end)
        # 원반을 목표 기둥으로 이동
        print(start, end)
        # 그룹(원반 N-1개)을 중간 기둥에서 목표 기둥으로 이동
        recursive(N-1, 6-start-end, end)

print(2**N-1)
recursive(N, 1, 3)

💡소요시간 : 48m