[BOJ] 하노이의 탑 이동 순서

하노이의 탑 이동 순서에 대해서 생각해보자

숫자가 높은 블록일수록 크기가 큰 블록이라고 할 때

1개를 옮기는 경우 : 1번 블록을 옮기면 됨 (1)

2개를 옮기는 경우 : 1번 블록을 옮긴 후 2번 블록을 옮기고 1번 블록을 2번 블록 위에 옮기면 됨 (121)

3개를 옮기는 경우 :  1~2번 블록을 옮긴 후 3번 블록을 옮기고 3번 블록 위에 1~2번 블록을 옮기면 됨( 121 3 121)

.....

다음과 같은 규칙성을 찾을 수 있다

n개를 옮기는 경우 : 1~n-1번까지 블록을 옮긴 후 n 번 블록을 옮기고 1~n-1번 블록을 n번 블록 위에 옮기면 됨 (단, n>=2)

..약간의 노가다로 일반항을 구하면 2^n -1 이라는것을 쉽게 알 수 있다 (xor아님)

 

몇 번 옮겨야 하는지에 대한 경우의 수는 비교적 쉽게 찾았지만... 문제는 옮기는 순서 ㅡㅡ

1 -> 3 번으로 옮기는 게 목표라고 할 때,

가장 마지막 블록을 제외한 나머지 블록을 순서대로 2번에 쌓은 후에 

마지막 블록을 3번에 놓고, 3번에 나머지 블록들을 순서대로 쌓으면 된다

또 1->2번으로 옮기는게 목표라면

가장 마지막 블록을 제외한 나머지 블록을 순서대로 3번에 쌓은 후에

마지막 블록을 3번에 놓고, 2번에 나머지 블록을 순서대로 쌓으면 된다

src->dst 번으로 옮기는게 목표라면

가장 마지막 블록을 제외한 나머지 블록을 순서대로 (6-src-dst)번에 쌓은 후에

마지막 블록을 dst에 놓고, dst에 나머지 블록을 순서대로 쌓는것이다

 

이를 바탕으로 코드를 짜면..

hanoi=[[],[],[]]

def solve(src,dst,count):
    global hanoi
    if count==1:
        #*기저사례*
        # 목적지가 3번인경우 3번에 놓아보고 놓을수있으면 놓고,
        # 놓을수 없다면 3번과 소스가 아닌 나머지에 놓아야 한다
        # 이를 위해 1+2+3 = 6 이라는점을 이용하자
        # 즉 src + dst + 나머지 = 6
        # 놓을 수있는 경우 일단 123 이렇게 놓이는걸 생각하면 앞에 추가 되어야한다
        # insert() 을 이용해야겠다 
        # 그리고 맨 마지막이랑 비교할게 아닌 맨 처음과 비교를 해야함
        if len(hanoi[dst-1])==0:
            #놓을수있따
            print(f'{src} {dst}')
            return hanoi[dst-1].append(hanoi[src-1].pop(0))
        if hanoi[dst-1][0] > hanoi[src-1][0]:
            #놓을수 있다 2
            print(f'{src} {dst}')
            return hanoi[dst-1].insert(0,hanoi[src-1].pop(0))
        #놓을수 없는 경우
        print(f'{src} {6-src-dst}')
        return hanoi[5-src-dst].insert(0,hanoi[src-1].pop(0))
    temp=6-src-dst
    solve(src,temp,count-1)
    solve(src,dst,1)
    solve(temp,dst,count-1)
    return

n=int(input())
hanoi[0] = list(range(1,n+1))
print(2**n-1)
solve(1,3,n)