코딩테스트 연습/백준

[백준-python] 11729번 : 하노이 탑 이동 순서(hanoi top in python)

슈퍼짱짱 2019. 8. 13. 09:00
반응형

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

 

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5

www.acmicpc.net


코드

# hanoi function def
def hanoi(n,a,b,c):
    if n==1:
        move.append([a,c])
    else:
        hanoi(n-1,a,c,b)
        move.append([a,c])
        hanoi(n-1,b,a,c)

move = [] # 이동 경로를 담을 list
hanoi(int(input()),1,2,3) # function 실행

print(len(move)) # 이동 횟수
print("\n".join([' '.join(str(i) for i in row) for row in move])) # 이동 경로 출력

코드설명

원판이 4일때를 예로들어 설명한다.

그림1

네 개의 원판을 1에서 3으로 모두 옮기기 위해서는 

먼저, 1,2,3번 세 개의 원판이 모두 2에 있어야 한다. (그래야 4번째 원판을 3으로 옮길 수 있기 때문)

그림2

그 전에, 세 개의 원판을 모두 2로 옮기기 위해서는 1,2번 두 개의 원판이 모두 3에 있어야 한다.

그림3

그 전에, 두 개의 원판 역시 마찬가지이다.

그림4

즉, 재귀를 이용해야 한다.

단, 순서는 n이 짝수일 때는 1번원판을 2번원판으로 먼저 이동,

홀수일 때는 1번원판을 3번원판으로 먼저 이동한다.

 

이때, 두 개의 원판을 한 곳으로 옮기는 그림4의 상황에서

2번 원판을 3에 옮기기 위해 1번 원판이 2에 있어야 하고,  ..... ①

2번 원판을 3으로 옮긴 후 ....................................................................... ②

다시 1번을 3으로 옮겨야 한다. ............................................................. ③

 

pseudocode로는 다음과 같다.

function f :

    f(1번 원판, 1->2) ... ①

    2번원판 1->3 ........ ②

    f(1번 원판, 2->3) ... ③

이 pseudocode를 일반화하면 위의 코드가 된다.


코드예시

 

ex) n=3

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

 

ex) n=4

15
1 2
1 3
2 3
1 2
3 1
3 2
1 2
1 3
2 3
2 1
3 1
2 3
1 2
1 3
2 3

 

ex) n=5

31
1 3
1 2
3 2
1 3
2 1
2 3
1 3
1 2
3 2
3 1
2 1
3 2
1 3
1 2
3 2
1 3
2 1
2 3
1 3
2 1
3 2
3 1
2 1
2 3
1 3
1 2
3 2
1 3
2 1
2 3
1 3

반응형