파이썬 알고리즘 116 번 | [백준 11729번] 하노이 탑 이동 순서

Yunny.Log ·2022년 2월 7일

Algorithm

목록 보기

119/318

116. 하노이 탑 이동 순서

1) 어떤 전략(알고리즘)으로 해결?

계속해서 반복되는 하노이 재귀
전 단계의 아이의 사이사이에 짝수개를 옮겨야 하면 사이사이 마다 1->2 , 2->3, 3->1 반복
홀수개를 옮겨야 하면 사이사이마다 1->3 3->2 2->1 반복

2) 코딩 설명

<내 풀이>


import sys
n = int(sys.stdin.readline())

def non_print_hanoi(num, fromm , by , to, first) : 
    global sum

    if(first==0):
        sum=0
        first+=1
    
    if(num==1) :
        sum+=1
    else : 
        non_print_hanoi( num-1, fromm, to , by, first)
        sum+=1
        non_print_hanoi( num-1, by, fromm , to, first)

def hanoi( num, fromm , by , to ) : 
    if(num==1) :
        print( fromm ,to )
    else : 
        hanoi( num-1, fromm, to , by )
        print( fromm ,to)
        hanoi( num-1, by, fromm , to )

non_print_hanoi(n,1,2,3,0)
print(sum)
hanoi(n,1,2,3)

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

출처 : 출처

1) 맞지만 시간 초과인 코드.. 최대 입력값인 20 넣으면 과부하


def hanoi(n, cnt)-> list :
    box=[]
    if n==1 : 
        return ["1 3"]

    elif n==2 :
        return ["1 2", "1 3", "2 3"]

    elif n%2==0: #짝수인 경우
        sel=["1 2", "2 3", "3 1"]
        for i in range(1,cnt+1):
            if(i%2==0) : #짝수인 경우
                m2=1
                cnt2=1
                for j in range(n-2):
                    cnt2+=2*(m2)
                    m2*=2        
                box.append(hanoi(n-1, cnt2)[i//2-1])
            else :#홀수인 경우-> 셀렉트 박스에서
                if i%3==1:
                    box.append(sel[0])
                elif i%3==0:
                    box.append(sel[1])
                else :
                    box.append(sel[2])
    else :
        sel=["1 3", "3 2", "2 1"]
        for i in range(1,cnt+1):
            m2=1
            cnt2=1
            for j in range(n-2):
                cnt2+=2*(m2)
                m2*=2  
            if(i%2==0) : #짝수인 경우
                box.append(hanoi(n-1, cnt2)[i//2-1])
            else :#홀수인 경우-> 셀렉트 박스에서
                if i%3==1:
                    box.append(sel[0])
                elif i%3==0:
                    box.append(sel[1])
                else :
                    box.append(sel[2])
    return box


if __name__ == "__main__" :
    n=int(input())
    cnt=1
    m=1
    for i in range(n-1):
        cnt+=2*(m)
        m*=2
    print(cnt)
res = (hanoi(n, cnt))
for i in res :
    print(i)

(2)
https://pacific-ocean.tistory.com/119

n개의 원판이 있을때, n - 1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을
1번에서 2번으로 옮긴 뒤, 맨 밑의 원판을 1번에서 3번으로 옮긴다.
그리고 n - 1개의 원판들을 다시 2번에서 3번으로 옮긴다.
n = int(input())
def hanoi(n, a, b, c):
    if n == 1:
        print(a, c)
    else:
        hanoi(n - 1, a, c, b)
        print(a, c)
        hanoi(n - 1, b, a, c)
sum = 1
for i in range(n - 1):
    sum = sum * 2 + 1
print(sum)
hanoi(n, 1, 2, 3)