[Python] 백준 11729번:하노이 탑 이동 순서 / 문제 풀이

[Python] 백준 11729번:하노이 탑 이동 순서 / 문제 풀이

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

11729번: 하노이 탑 이동 순서

---

º 문제 파악 

[Start] (A, B, C)	[1]	[2]	[3]	[4]	[5]	[6]	[7]
1      2      3      _ _ _	2        3    1  _ _ _	3 2 1 _ _ _	1   3 2   _ _ _	1      2 3   _ _ _	1 2 3 _ _ _	2 1    3 _ _ _	1       2       3 _ _ _

  총 7번의 움직임으로 3개의 원판을 첫 번째에서 세 번째로 옮겼다. 편하게 순서대로 A, B, C라고 말하겠다.    재귀 함수의 문제를 풀기 위해서는 원래와 같지만 더 작은 형태의 움직임이 반복되는 것을 파악해야 한다. 이  함수 이름을 hanoi라고 한다면, hanoi(N) 은 N개의 원판을 다른 곳으로 옮겨라!  그리고 hanoi(N-1)은 N-1개의 원판을 다른 곳으로 옮기라는 말이다. 

 [Start] ~ [3]까지의 과정이 2개의 원판을 A에서 B로 옮긴 것이다. 그리고 [4]는 가장 큰 원판을 한 개 A에서 C로 옮긴 것, 그리고 [5] ~ [7]의 과정은 2개의 원판을 B에서 C로 옮겨 최종적으로 모두 옮긴 것이다! 그렇다면 N개의 원판을 옮길 때 hanoi(N-1) -> 1개 옮기기 -> hanoi(N-1)의 과정을 거친 것이다. 한 개를 옮기는 건 move라 표현해보자.

 

 결국 A에서 C로 B를 이용해서 원판을 옮겼다. 이 생각을 이용해서 문제를 풀어보자

 

 문제에서 요구하는 사항은 몇 번을 옮겼고, 각 움직임마다 어디에서 어디로 갔는지이다. 그렇다면 하노이 함수와 무브 함수를 구현한다면 이런 식일 것이다. 

( 본 함수는 맨 밑에 있는 도움이 된 사이트에서 복사한 것에서 문제에 맞게 수정한 것, 내가 짠 것은 아님)

def hanoi(N, start, to, via):
    if N == 1:
        move(1, start, to)
    else:
        hanoi(N-1, start, via, to)
        move(N, start, to)
        hanoi(N-1, via, to, start)

def move(N, start, to):
    print(start+' '+to)
    
# https://shoark7.github.io/programming/algorithm/tower-of-hanoi#7

 

º 코드

def hanoi(N, start, to, via):
    if N == 1:
        move(1, start, to)
    else:
        hanoi(N-1, start, via, to)
        move(N, start, to)
        hanoi(N-1, via, to, start)

def move(N, start, to):
    print(start+' '+to)

num = int(input())
print(2**num -1)
hanoi(num,'1','3','2')

 

 

º  도움이 된 사이트

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

'하노이의 탑' 이해하기