[BOJ] #1914-하노이 탑

1914 하노이 탑

하노이 탑 알고리즘을 사용하여 첫번째 에서 세번째(마지막) 막대로 이동시키는 과정과 이동 횟수를 출력하는 문제

문제
.
.

📌 요구사항 및 조건

• N은 1보다 크거나 같고 100보다 작거나 같다.
• 단, N이 20보다 큰 경우에는 과정을 출력할 필요가 없다
• (N이 20을 넘으면 이동 횟수만 출력)
• 출력은 두 정수 A B 빈칸을 사이에 두고 출력
  - A번째 탑 가장 위에 있는 원판을 B번째 탑(마지막)의 가장 위로 옮긴다는 뜻

.
.
.
.
.
.

문제풀이 순서

1️⃣ 원판의 총 개수 입력 받기

2️⃣ 총 이동횟수 구하기

3️⃣ 입력받은 원판의 갯수가 20보다 크거나 같은지 비교 후 함수 실행

4️⃣ 하노이 탑 함수 구현

• 함수에 필요한 매개변수 생각해보기
• 원판이 어떤 방식으로 움직이는지 생각해보기

.
.
.
.
.
.
.

전체 코드

import sys

input = sys.stdin.readline

def move(n, start, end):
    if n == 1:
        print(start, end)
        return
    
    move(n-1, start, 6 - start - end)
    print(start, end)
    move(n-1, 6 - start - end, end )

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

코드 설명

• n: 이동해야 하는 원반 개수
• start: 원반이 처음 위치한 기둥
• end: 원반을 옮길 목표 기둥
• 6 - start - end: 보조 기둥 (하노이의 법칙: 기둥 번호 1, 2, 3의 합이 항상 6)

하노이 탑 재귀의 핵심 개념

• 원반이 하나면 직접 이동 (n == 1)
  - 기둥 start → end로 이동하면 끝.
• 원반이 n개면
  - n-1개의 작은 원반을 보조 기둥(aux)로 이동.
  - 가장 큰 원반을 목표 기둥(end)으로 이동.
  - n-1개의 작은 원반을 목표 기둥(end)으로 이동.

실행 과정

move(3, 1, 3)
├── move(2, 1, 2)   # (1) 작은 원반들을 보조 기둥(2)로 이동
│   ├── move(1, 1, 3) → "1 3" (원반 1 이동)
│   ├── print(1, 2)  → "1 2" (원반 2 이동)
│   ├── move(1, 3, 2) → "3 2" (원반 1 이동)
│
├── print(1, 3)      → "1 3" (가장 큰 원반 이동)
│
├── move(2, 2, 3)   # (2) 작은 원반들을 목표 기둥(3)으로 이동
│   ├── move(1, 2, 1) → "2 1" (원반 1 이동)
│   ├── print(2, 3)  → "2 3" (원반 2 이동)
│   ├── move(1, 1, 3) → "1 3" (원반 1 이동)