코딩 테스트/백준

[Python] 백준 11729 하노이 탑 이동 순서

위시리 2025. 2. 10. 13:57

 

문제 분석

  • 모든 원판을 첫번째 장대 → 세번째 장대
  • 한 번에 한 개의 원판만 움직일 수 있다.
  • 쌓인 원판은 항상 위에 있는 원판이 아래 있는 원판보다 작아야 한다.
  • 크기 = 인덱스

  • 처음 원반이 높인 기둥 : start 
  • 목적지의 기둥 : end
  • 중간에 있는 기둥 : tmp
  • 가장 큰 원반을 제외한 나머지 원반들이 쌓여있는 것을 그룹이라고 할 때
  • 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 가장 먼저 '그룹'을 중간 기둥으로 옮겨야 한다.

  • 그러면 그 그룹은 또 어떻게 옮길 것인가?
    • 이전과 동일한 방식으로 맨 아래 원반을 제외한 그룹' 원반만 옮긴다.

 

코드 설계

..

 

정답 코드

다른 사람 코드 1

https://velog.io/@miiingirok/%EB%B0%B1%EC%A4%80-1914.-%ED%95%98%EB%85%B8%EC%9D%B4%ED%83%91-Python

import sys
input = sys.stdin.readline

n = int(input())
def hanoi(n, a, b, c) :
    if n == 1 :
        print(a,c)
    else :
        hanoi(n-1, a, b, c) # 1단계
        print(a,c) # 2단계
        hanoi(n-1, b, a, c) # 3단계
        
sum = 2**n - 1
print(sum)

hanoi(n, 1, 2, 3)

풀이

1. 막대를 옮기는 과정

📌1단계 : n-1개의 원판을 1번막대에서 2번막대로 옮긴다.
그런데 여기서 의문점이 발생한다.

1) 저렇게 옮기는 경우가 최소인것일까?
2) 어떻게 옮기는 것일까?

1번 질문의 경우, 하노이탑을 잘 알고 계시다면 잘 이해할 수 있는 부분이지만 그게 아니라면 아래 영상을 2분 54초부터 보면 된다.
https://www.youtube.com/watch?v=fffbT41IuB4

2번 질문 : 재귀 알고리즘을 사용하면 쉽게 해결할 수 있다. 따라서 이 문제는 재귀함수를 이용하여 푸는 문제라고 볼 수 있다.

📌 2단계 : 남은 1개(마지막) 원판을 1번 막대에서 3번 막대로 옮긴다.

📌 3단계 : 다시 n-1개의 원판을 2번 막대에서 3번 막대로 옮긴다.
이 1, 2, 3단계가 핵심 아이디어이다.

2. 이동횟수
이동횟수를 구하는 과정도 한번 살펴보자.
count를 사용해도 되는데 뒤에서 안 되는 이유를 자세히 살펴보겠다. 지금은 나열을 해보며 규칙성을 먼저 찾아보자
N이 원판개수일 때, 이동횟수 : 
N = 1 → 1N = 2 → 3N = 3 → 7N = 4 → 15N = 5 → 31
1열로 나열해보면 1, 3, 7, 15, 31…이 된다.
이를 통해 2n−1+1 임을 확인할 수 있다. 이 식은 이동횟수를 출력할 때 활용하면 된다.

 

다른 사람 코드 2

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

def f(n, a, b, c):
  if(n == 1):
    print(a, c, sep = " ")
  else:
    f(n-1, a, c, b) #1단계
    f(1, a, b, c) #2단계
    f(n-1, b, a, c) #3단계

n = int(input()) #입력
print(2**n-1) #이동횟수 출력
if(n <= 20): #함수 조건
  f(n, 1, 2, 3) #함수 호출

풀이

 원판이 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단계만 작성하면 됩니다.

저작자표시