(Python/🥈1)백준 알고리즘 11729번: 하노이 탑 이동 순서

문제  출처:https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

 

알고리즘의 벽이라고 불리는 하노이의 탑문제이다..

n = 2 인 경우에는 1+2    =3

n = 3 인 경우에는 1+2+4   = 7

n = 4 인 경우에는 1+2+4+8     = 15

총 이동횟수는 2^n - 1 이다

 

이런식으로 옮긴횟수 공식은 쉽게 찾았지만 수행 과정 출력하는것에 애를 먹었다.

 

풀이:

def hanoi(N,i,j,via):           #
    if N == 1:
        print(i,j)
    else:
        hanoi(N-1,i,via,j)
        print(i,j)
        hanoi(N-1,via,j,i)

N = int(input())
print(2**N-1)
hanoi(N,1,3,2)

>>
def hanoi(N,시작점,목표점,경유점):
    if N == 1:
        print(시작점,목표점)
        return
    else:
        hanoi(N-1,시작점,경유점,목표점)  # 경유지역에 큰거 빼고 다 집어넣음
        print(시작점,목표점)           # 가장큰거 목표점에 넣고
        hanoi(N-1,경유점,목표점,시작점)  # 원래 시작지역이 경유지역이 / 원래 경유지역이 시작점이 된다

 

가장 큰 원반을 목표기둥에 넣고나면 없다 생각하고 

그거보다 작은 원반을 목표기둥에 넣으려면 원래 보조기둥을 시작기둥으로  시작기둥을 보조기둥으로 바꿔서 하면 된다

 

이걸 코드로 나타내면 hanoi(n-1,via, j,i) 이다

 

 

이 문제의 흐름을 코딩으로 나타내면 

hanoi(3,1,3,2)
    hanoi(2,1,2,3)
        hanoi(1,1,3,2)
        hanoi(1,3,2,1)
    hanoi(2,2,3,1)
        hanoi(1,2,1,3)
        hanoi(1,1,3,2)

 

 

 

문제를 풀고 이 영상을 보니 소름돋게 이해가 잘된다. 꼭 봐줬으면 좋겠다.

https://www.youtube.com/watch?v=FYCGV6F1NuY