백준 11729번 파이썬 풀이

안녕하세요 오늘은 하노이탑을 옮기는 경로를 구하는 코드를 짜보겠습니다.

이 문제는 재귀 카테고리에 있던 문제이므로, 재귀를 이용하여 풀어보겠습니다. 

우선 원리를 설명해보겠습니다.

위 gif를 보시면 이해가 좀 더 수월할겁니다. gif에서는 원판 4개 갖고 설명을 했지만, 원판 n개일때를 생각해보면서 설명을 해보겠습니다. 원판이 n개일때 이동 방법은, 첫번기둥에 있는 n-1개의 원판을 2번째 기둥에 옮기고, 제일 큰 원판을 세번째 기둥으로 옮기고(1,3) 다시 n-1개의 원판을 세번째 기둥으로 옮겨서 완성한다. 이 재귀를 코드로 표현하겠습니다.

코드:

a = int(input())
res_a = pow(2, a)-1
print(res_a)
def Hanoi(n):
    if n==1:
        return ['1', '3']
    else:
        Hanoi_3 = []
        Hanoi_2 = []
        Hanoi_4 = []
        Hanoi_nm = Hanoi(n-1)

        for i in Hanoi_nm:  #2를 4로 변환
            temp = i.replace("2","4")
            Hanoi_4.append(temp)
        for i in Hanoi_4: #3을 2로 변환
            temp = i.replace("3", "2")
            Hanoi_2.append(temp)
        for i in Hanoi_2: #4를 3으로 변환
            temp = i.replace("4", "3")
            Hanoi_3.append(temp)

        li = Hanoi_3 + ['1', '3']
        Hanoi_1 = []
        Hanoi_2 = []
        Hanoi_4 = []
        for i in Hanoi_nm:  #1를 4로 변환
            temp = i.replace("1","4")
            Hanoi_4.append(temp)
        for i in Hanoi_4: #2을 1로 변환
            temp = i.replace("2", "1")
            Hanoi_1.append(temp)
        for i in Hanoi_1: #4를 2으로 변환
            temp = i.replace("4", "2")
            Hanoi_2.append(temp)
        li += Hanoi_2
        return li

res_li = Hanoi(a)
for i in range(1, int(len(res_li)/2 + 1)):
    print(res_li[2*i-2],res_li[2*i-1])