백준 파이썬 11729 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

코드

n = int(input())

def hanoi(n,start,end):
    if n == 1:
        print(start,end) # 원판이 하나만 남았다면 목표기둥으로 옮긴다
        return
    hanoi(n-1,start,6-start-end) # 가장 큰 원판 위에 있는 n-1개의 원판을 보조기둥으로 옮긴다
    print(start,end) # 가장 큰 원판을 목표기둥으로 옮긴다
    hanoi(n-1,6-start-end,end) #보조기둥에 있는 n-1개의 원판을 목표기둥으로 옮긴다

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

 

이 문제를 푸는 핵심 아이디어는, 가장 큰 원반을 제외한 나머지 원반들을 모두 보조기둥으로 옮기고, 가장 큰 원반을 목표 기둥으로 옮기는 것 입니다.

맨 처음 1번기둥을 시작기둥, 2번기둥을 보조기둥, 3번기둥을 목표기둥이라고 하면

1번기둥, 2번기둥, 3번기둥의 합은 6입니다. 따라서 보조기둥은 (6-시작-목표)번 기둥 입니다.

n개의 원반이 있으면, n-1개의 원반을 보조기둥(6-시작-목표) 으로 옮긴 후,

n번 원반을 목표 기둥으로 이동시키고 n = n-1 이라고 생각하고 문제를 처음부터 다시 풀면 됩니다.

 

 

 

n=3 일때를 예시로 들어보겠습니다.

 

1번기둥(시작), 2번기둥(보조), 3번기둥(목표)이 있습니다.

그리고 1번 기둥에 존재하는 가장 큰 원반을 3번원반, 그 위의 원반을 2번 원반, 또 맨 위에 있는 원반을 1번 원반이라고 하겠습니다.

 

3번 원반을 3번 기둥의 맨 밑으로 옮겨놔야, 정답을 구할 수 있는 최소 조건을 만족합니다.

따라서 3번 원반을 제외한 2개의 원반(2,1) 을 2번 기둥으로 옮겨놓고, 3번 원반을 3번 기둥으로 옮겨야 합니다.

 

1번 원반을 3번 기둥으로 옮긴 뒤, 2번 원반을 2번 기둥으로 옮기고, 다시 1번 원반을 2번 기둥으로 옮깁니다.

그 후, 3번 원반을 3번 기둥으로 옮기면 됩니다.

 

지금부터는 3번 원반은 제외시키고 n=2라고 생각하여 문제를 처음부터 다시 풀면 됩니다.

(3번 원반은 가장 큰 원반이며, 목표 기둥 맨 밑에 있기 때문에 사실상 없는 원반이라고 생각할 수 있습니다.)

 

이제 문제를 리셋시키고 n=2라고 생각합니다.

모든 원반이 2번 기둥에 있기 때문에 2번 기둥이 시작기둥이 되고, 1번기둥은 보조기둥이 됩니다.

 

2번 원반이 3번기둥(목표기둥) 으로 가려면 먼저 1번 원반이 1번기둥(보조기둥)으로 가야합니다.

1번 원반을 1번기둥(보조기둥)으로 옮긴 후, 2번 원반을  3번기둥(목표기둥)으로, 마지막으로 1번 원반을 3번 기둥으로 옮깁니다.

 

 

 

 

https://www.youtube.com/watch?v=FYCGV6F1NuY