[BOJ] 11729번

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

11729번: 하노이 탑 이동 순서

 

하노이 탑 알고리즘

참조 <백준 하노이탑 이동 순서>

위와 같이 하노이 탑을 시작 장대에서 목적 장대까지 이동시키위해 원판을 움직이는 방식에 대한 알고리즘이다. 이때 한번에 한 개의 원판만을 옮길 수 있고 쌓아져 있는 원판은 항상 위의 원판이 아래 것보다 작아야한다.

 

원판이 1개라면,

1번 장대에서 3번 장대로 1번 원판을 움직인다. 1->3

 

원판이 2개라면,

1번 장대에서 2번 장대로 1번 원판을 움직인다. 1->2

1번 장대에서 3번 장대로 2번 원판을 움직인다. 1->3

2번 장대에서 3번 장대로 1번 원판을 움직인다. 2->3

 

원판이 3개라면, 

1번 장대에서 2번 장대로 1&2번 원판을 움직인다.

1번 장대에서 3번 장대로 3번 원판을 움직인다.

2번 장대에서 3번 장대로 1&2번 원판을 움직인다.

 

즉 원반이 n개라면,

1번 장대에서 2번 장대로 n-1개의 원판을 움직인다.

1번 장대에서 3번 장대로 n번째 원판을 움직인다. 

2번 장대에서 3번 장대로 n-1개의 원판을 움직인다.

 

n번째의 원판을 옮기기 위해 n-1개의 원판을 움직이는 방식을 생각하고, n-1번째 원판을 옮기기 위해 n-2개의 원판을 움직이는 방식을 생각하는 재귀적인 방식이다.

원판을 움직이는 횟수는 총 2**n-1번이다.

 

Python3

def hanoi(n, from_pos, to_pos, mid_pos):
    if n == 1:
        print(from_pos, to_pos)
        return 
    hanoi(n-1, from_pos, mid_pos, to_pos)
    print(from_pos, to_pos)
    hanoi(n-1, mid_pos, to_pos, from_pos)


if __name__ == '__main__':
    N = int(input())
    print(2**N-1)
    hanoi(N, 1, 3, 2)

hanoi탑 이동을 위한 함수를 만들었다. 우선 1개의 원판을 옮길 때는 단순히 시작 장대에서 목적지로 이동시키면 되기 때문에 출력 후 return한다. 위에서 설명했던 하노이 탑 알고리즘대로 hanoi함수를 통해 n-1개 원판이 보조 장대로 이동하는 방식을 구하고 n번째 원판을 이동 시킨 후 n-1개의 원판을 다시 목적 장대로 이동시키는 방식을 구한다.

장대 구분을 위해 함수에서는 매개변수로 from_pos(시작 장대), to_pos(목적 장대), mid_pos(보조 장대)로 정하였다. 재귀 호출 시에 매개변수를 맞춰 적어주었다.

main함수에서는 입력받은 n에 대해서 이동 횟수 출력 후 hanoi함수를 호출했다. 이때 1번 장대를 시작 장대, 3번 장대를 목적 장대, 2번 장대를 보조 장대로 하여 구하였다.