11729번 - 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

solve 함수는 재귀 함수이다. 원반이 하나라면 그냥 옮기면 끝이기 때문에 종료조건으로 설정한다.

from_pos, to_pos, aux_pos 각각을 시작점, 도착점, 보조점이라고 생각한다.

 

즉, solve(N, 1, 3, 2) 는 N개의 원판을 1번 기둥을 시작으로 3번 기둥으로 옮기되 2번 기둥을 보조기둥으로 사용한다는 뜻이다.

 

하노이의 탑 문제에서 가장 중요한 것은 가장 큰 원반을 도착점에 둔 후, 나머지를 도착점에 옮기면 된다는 것이다. 이때 보조점을 사용한다. 

# 하노이 탑 이동 순서
import sys
input = sys.stdin.readline

N = int(input())

def solve(N, from_pos, to_pos, aux_pos):
    if N == 1:
        print(from_pos, to_pos)
        return
    solve(N-1, from_pos, aux_pos, to_pos)
    print(from_pos, to_pos)
    solve(N-1, aux_pos, to_pos, from_pos)
    
print(2**N-1)
solve(N, 1, 3, 2)