[11729] 하노이 탑 - Python

코딩메이트에게 이 문제가 "뉴비들이 제일 처음 대가리 깨지는 문제"라는 무시무시한 이야기를 듣고 바로 도전해 봤다. 

 

문제

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

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

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

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

내 코드

result=[]

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

hanoi(int(input()), 1, 2, 3)
print(len(result))
for i in result:
    print(i[0], i[1])

 

과정

머릿속으로 원판을 옮기는 과정을 시뮬레이션 하다 보니 자꾸 까먹어서 그림을 그리면서 과정을 생각해 봤다. n=3까지 직접 해보니 규칙을 발견할 수 있었다.

 

포인트는 제일 아래에 있는(제일 큰) 원판을 세 번째 장대로 옮기고 나서 나머지 원판들을 그 위에 쌓아야 한다는 것이다. 제일 큰 원판을 옮길 수 있는 경우의 수는 단 한가지밖에 없다. 한 장대에는 제일 큰 원판 하나만 있고, 한 장대에는 원판이 하나도 없으며 나머지 한 장대에 남은 원판이 모두 있는 경우 뿐이다. 즉 원판이 n개일 때의 과정을 분리해 보면 제일 큰 원판을 제외한 n-1개의 원판을 모두 두 번째 장대로 옮기고 -> 제일 큰 원판을 세 번째 장대로 옮긴 후 -> 역시 남은 n-1개의 원판을 세 번째 단계로 옮기는 세 단계다.

 

정리하면 다음과 같다.

• 원판이 n개일 때의 이동 과정:
  1. 원판이 n-1개일 때의 과정에서 두번째, 세번째 장대를 맞바꾼 과정
  2. 첫번째 장대에서 세번째 장대로 이동
  3. 원판이 n-1개일 때의 과정에서 첫번째, 두번째 장대를 맞바꾼 과정

원판이 n개일 때의 과정을 n-1일 때의 과정에서 모두 얻을 수 있으므로 재귀함수로 코드를 짜면 된다.

 

사실 문제를 풀기 시작한 지 얼마 지나지 않아 코드를 완성했고, 출력이 잘 나오길래 머야 쉽넹ㅋ 하고 있었는데

;;

?

시간 초과가 떴다.

 

처음에 썼던 코드는 장대 순서를 바꾸는 함수를 따로 작성해서 구현되었는데, 함수 호출 과정이 재귀 함수에 더해지니 시간이 오래 걸린 듯 하다. 깐깐한 백준..

import copy

def convert(arr, a, b):
    res = []
    for i in arr:
        temp = copy.deepcopy(i)
        for j in range(len(temp)):
            if(temp[j] == a):
                temp[j] = b
            elif(temp[j] == b):
                temp[j] = a
        res.append(temp)
    return res 
    
def hanoi(n):
    if(n == 1):
        return [[1,3]]
    else:
        return convert(hanoi(n-1), 2, 3) + [[1,3]] + convert(hanoi(n-1), 1, 2)
        
res = hanoi(int(input()))
print(len(res))
for i in res:
    print(i[0], i[1])

이게 처음에 썼던 코드다. 핵심 알고리즘은 똑같다.

이제 보니 하노이 코드보다 순서 바꾸는 코드가 더 긴게 좀 별로긴 하다. 시간 초과를 보고 저 convert 함수를 삭제해야겠다는 생각이 들어 hanoi()에 각 장대의 번호를 인자로 전달하고, 그 번호의 순서를 바꿔 재귀 호출을 하도록 수정했다.

 

...

보기 좋은 코드가 효율도 좋은 것 같다.