[백준 11729번] 하노이 탑 이동순서 - Python(파이썬) 자세한 풀이

1. 문제

 

백준 11729번

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

11729번: 하노이 탑 이동 순서

 

2. 아이디어

우리는 원판이 1개일때 정답은 매우 당연하게 알고있습니다!

그냥 하나를 옮기면 되죠 ㅎㅎ

 

그렇다면 원판이 n개일때는 어떨까요?

n에 대하여 생각해보세요!

 

음.. 그림을 보실까요?

위 그림에서 우리는 n개의 원판을 세번째 막대(?)에 옮길려고 합니다.

편의상 막대를 1번, 2번, 3번 막대라 하겠습니다.

이렇게요.

그럼 이제 n개의 원판을 1번 막대에서 3번 막대로 옮기는 것을 나눠서 생각해봅시다.

총 3단계로 나뉘는데요. (이해를 돕기 위해 변화가 있는(옮겨진) 원판은 색을 노란색으로 했습니다.)

 

위 그림 처럼

1단계 에서는 n-1개의 원판을 1번 막대에서 2번 막대로 옮깁니다.

여기서 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단계가 이 문제를 푸는 핵심 아이디어 입니다!

 

3. 풀이

(1) 코드

def hanoi_tower(n, start, end) :
    if n == 1 :
        print(start, end)
        return
       
    hanoi_tower(n-1, start, 6-start-end) # 1단계
    print(start, end) # 2단계
    hanoi_tower(n-1, 6-start-end, end) # 3단계
    
n = int(input())
print(2**n-1)
hanoi_tower(n, 1, 3)

(2) 해설

 

 오 코드가 매우 짧죠?! (행복하시죠?)

hanoi_tower 라는 이름의 재귀 함수를 선언했습니다.

그런데 start, end라는 변수가 존재하는 것을 알 수 있습니다.

바로 n개의 원판을 '몇번 막대에서 몇번 막대로 옮길거야'의

데이터를 담고 있는 변수들입니다. 즉, 1, 2, 3중 하나가 start, end 각각에 저장되어

(당연히 start, end는 서로 다른 값이겠죠? ㅎㅎ)

start번 막대에서 end번 막대로 옮겨라! 라는 정보를 담고 있는 것입니다.

 

따라서 

1단계 에서는 start 막대에서 6-start-end 막대로 옮겼는데

위 그림을 참고하시면 아시겠지만 1단계에서는, start 막대(그림에서 1번 막대)에 있는

n개의 원판 중 n-1개의 원판을 end 막대(그림에서 3번 막대)가 아닌 2번 막대로 옮기는 것을 보실 수 있습니다.

그런데 우리는 start와 end 막대의 번호만을 알고 있을 뿐 나머지 막대의 번호는 알지 못합니다!

그러나!! 우리는 start막대와 end막대 그리고 번호 모를 막대의 번호를 다 합치면 6이 된다는 사실(1+2+3)을 알고있으므로 결국, 6에서 start와 end를 빼주면 번호 모를 막대의 번호를 알게 되는 것이죠!

 

2단계에서는 그림과 같이 start 막대에서 end막대로 옮겨주면 됩니다.

 

3단계의 경우 1단계와 마찬가지의 메커니즘이 작동합니다!

 

오늘도 봐주셔서 감사합니다~! (댓글, 공감눌러주는 센스~ㅎㅎ)

p.s. 질문과 오류 지적은 언제나 환영입니다.