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

📎문제링크: https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

💼서론 

예전에 한번 맛보다가 잘 모르겠어서 북마크 남기고 있던 문제였는데, 스터디를 통해 책임감을 갖고 다시 풀어보기 위해 이 문제를 스터디에서 택했다

 

🧩문제 해석

재귀! 하면 빠질 수 없는 하노이탑
원판의 갯수가 주어졌을 때 이동횟수와 이동경로를 출력하시오 

 

📀원판 이동 횟수

원판의 이동 횟수 구하는 것은 쉽게 유추해냈다.
n개의 원판을 이동시키는 것은 n-1개의 원판을 이동시킨다음 제일 밑에 있는 원판 하나를 목표 장대에 옮기고 다시 n-1개의 원판을 이동시키는 것이다. 
즉 a(n) = a(n-1)+1+a(n-1) 인것이다.
a(1) = 1, a(2)= 3 이다. 
이게 내 코드에서는 함수 hanoi_top_cnt() 로 구현되었다.

하노이 탑 이동횟수

 

 

🏃‍♂️원판 이동 경로🏃‍♀️

 

어려운 것은 이부분이었다. 열심히 A4용지에 끄적끄적하여 규칙을 알아내는대에는 성공했지만 코드구현까지는 아쉽게도 실패하였다. 담번에 다시 다른 방법으로 도전해볼것이닷!

낙서끄적끄적

낙서도 다음번에는 티스토리에 개시할거 생각하고 조금더 알아보기 쉽고 간결하게 적어야지..ㅎ 아무생각없이 적고 올려보니 너무 난잡(?)

 

원판 이동의 기본적인 매커니즘은 앞서 말했다시피 원판 n개가 있으면 원판 n-1개를 목표 장대가 아닌 나머지 장대에 옮기고 제일 큰 원판을 목표 장대에 옮기고, 다시 n-1개의 원판을 목표 장대에 옮긴다.

 

1. n-1개의 원판을 목표장대가 아닌 나머지 장대에 옮김

2. 제일 큰 원판을 목표 장대로 옮김

3. n-1개의 원판을 목표장대로 옮김

 

 

이것이 하노이 탑 원판을 옮기는 최소경로이다.

 

하노이 탑 이동 경로

 

중간에 6-start-end가 보이는데 이것이 의미하는 바는 "현재 있는곳도 아니고 그리고 목표지점이 아닌 곳" 이다.

장대가 1,2,3 이렇게 있다. 현재 n개의 원판이 1에 위치하고 마지막 원판을 3에 위치시켜야 한다면, n-1개의 원판은 2에 위치시켜야 한다. 즉 현재위치(1)와 목표장대(3)가 아닌 곳으로 n-1을 이동시켜야 하는데 장대는 1,2,3개 있기에 6-1-3 하면 n-1원판의 이동위치(2)가 나온다.

 

 

💻코드

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

def hanoi_top_cnt(n):
    if n == 1:
        return 1
    else:
        return hanoi_top_cnt(n-1)*2 + 1

n = int(input())
print(hanoi_top_cnt(n))
hanoi_top_move(n, 1, 3)