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

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

예제 입력 1

3

예제 출력 1

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

 

 

---

하노이의 탑은 알고리즘에서도 꽤나 유명한 문제로 알고있다.

예전에 푼 것 같지만 기억이 나질 않는다... 내 기억력...

 

우선 하노이의 탑에서

제일 중요한 룰은

1. 마지막을 제외한 위에 있는 블록을 모두 보조 봉에 놓는다.
2. 마지막 블록을 목표한 봉에 놓는다.
3. 보조 봉에 있는 나머지 블록을 모두 목표 봉에 놓는다.

 

이 룰들만 알고 있으면 쉬워진다.

예를 들어보자. 시작봉(1), 보조봉(2), 목표봉(3)

총 2개의 블록이 목표봉인 3번에 가야한다.

맨 밑의 블록이 우선 목표한 봉(3) 가기 위해서

 

룰 1번을 실행한다. 맨 위의 블록을 보조 봉에 넣는다.

룰 2번 맨 밑 블록을 목표봉에 넣는다.

마지막으로 룰 3번을 실행해서 나머지 블록을 목표봉에 넣는다.

 

간단하다.

 

이번엔 총 3개의 블록으로 예를 들어보자.

 

1. 마지막 블록을 제외한 모든 블록을 보조 봉에 넣어야한다.

   - 여기서 2개의 블록이므로 한번에 2개의 블록을 이동시킬 수 없다.

   - 1번 안에서 룰을 순번대로 실행해준다.

   - 2개의 블록이 보조 봉(2번)으로 가야하는것이 목표다.

   1 -1. 2개중 젤 위의 블록을 목표하는 2번이 아닌 3번에 넣는다.(왜냐하면 지금의 목표봉은 2번, 보조봉은 3번이기 때문에)

   1 -2. 2개중 마지막 블록이 목표하는 2번 봉에 넣는다.

   1 -3. 보조봉(3번)에 있는 나머지 블록을 목표하는 2번에 넣는다.

 

---- 이러면 방법 1번이 끝났다!!-----

 

2. 맨 밑에 있던 3번 블록을 목표봉(3번)에 넣는다.

 

3. 마지막으로 보조봉(2번)의 블록 2개를 목표봉에 넣는다.

   - 하지만 또 여기서 두개를 동시에 움직일 수 없고

   - 맨 위의 블록이 먼저 목표하는 곳에 들어갈 수 없으므로!!

   - 또 3번 안에서 룰 대로 진행해줘야한다.

   3 -1. 2개의 블록 중 젤 위의 블록을 목표하는 3번이 아닌 보조봉 1번에 넣는다.(지금은 시작봉(2번)이니깐)

   3 -2. 이제 2번 봉에 있는 한 개의 블록을 목표하는 3번봉에 넣는다.

   3 -3. 마지막으로 보조봉(1번)에 있는 블록을 목표봉(3번)에 넣는다.

 

끝이다.---------------------------------------------------------------------------------------------------------------------------

 

이렇게 룰 3개로 모든 것이 끝났다.

블록이 4개일 때, 5개 일때도 이렇게 똑같이 진행된다.

1번안에서 세부적으로 룰대로 돌리고 3번안에서 세부적으로 룰대로 돌아가고..

 

이것을 알고리즘화 하면

n=int(input())

def hanoi_top(n, start, target, assi):
	if n==1:
    	print(start, target)
        return
    
    hanoi_top(n-1, start, assi, target)  # 룰1
    print(start, target)                 # 룰2
    hanoi_top(n-1, assi, target, start)  # 룰3
    

print(2**n-1)
hanoi_top(n, 1, 3, 2)

(룰1) 이렇게 마지막을 제외한 모든 블록을 보조봉으로 옮기고 start ->target 이던 것이 start->assi로 바뀐다. 

(룰2) 그리고 마지막 블록을 목표블록으로 옮긴다.

(룰3) 마지막으로 보조봉에 있는 나머지 블록들을 목표블록으로 옮긴다. assi->target

 

만약 룰1과 룰3에서 블록이 2개 이상이라면 그 안에서 룰이 돌아간다~

 

 

이 블로그(https://data-jj.tistory.com/34)에서 소개한 유튭영상이 매우 도움이 된다.

https://youtu.be/FYCGV6F1NuY