백준 11729번 풀이

문제

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

11729번: 하노이 탑 이동 순서

하노이의 탑에서 이동 경로와 최종 이동 횟수를 출력하시오. (입력: 원판 개수)

 

Reference

https://ko.wikipedia.org/wiki/하노이의_탑

하노이의 탑 - 위키백과, 우리 모두의 백과사전

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

https://8iggy.tistory.com/100

재귀 함수 - 하노이의 탑

https://soohyun6879.tistory.com/m/190

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

 

풀이

정말 의외로 심플하게 풀렸다. (실화)

 

하노이의 탑? 

퍼즐 게임이다. 막대기 세 개와 크기가 다른 원판이 있고 이걸 맨 끝에 있는 막대로 옮기면 되는데 규칙이 있다.

1. 원판은 한번에 하나씩 옮길 수 있다.
2. 원판은 맨 위에 것만 옮길 수 있다.
3. 큰 원판이 작은 원판 위에 오면 안된다.

참 쉽죠?

def hanoi(number_of_disks_to_move, from_, to_, via_):
    if number_of_disks_to_move == 1:
        print(from_, "->", to_)
    else:
        hanoi(number_of_disks_to_move-1, from_, via_, to_)
        print(from_, "->", to_)
        hanoi(number_of_disks_to_move-1, via_, to_, from_)

하노이의 탑 코드를 보면 이렇게 입력 인자가 4개이다. (원판 개수, 어디서, 어디로, 어디를 통해) 개수 말고 세 개는 시작 기둥, 끝 기둥, 보조 기둥이다. 그럼 입력인자 다이어트가 되나요?

import sys
a = int(sys.stdin.readline())
def hanoi(n,start,to,via):
    if n == 1:
        print('{} {}'.format(start,to))
    else:
        hanoi(n-1,start,via,to)
        print('{} {}'.format(start,to))
        hanoi(n-1,via,to,start)
print(2 ** a - 1)
hanoi(a,1,3,2)

아뇨 그냥 입력인자 중 기둥을 고정값으로 두시면 됩니다. 이동 횟수도 재귀하면서 셀 필요 없이 2^n-1 하면 된다. (n=원판 개수)