백준-1914-하노이 탑

하노이 탑 알고리즘

• 하노이 탑 알고리즘은 다음을 참조했습니다

[python] 파이썬-재귀 함수 고전 예제: 하노이 탑(해설 강의 有)

 

#하노이 탑에서 필요한 요소를 모두 매개변수로 받습니다.
하노이탑(원판, "시작기둥"에서 "대상기둥"으로 "보조기둥"을 활용해서):
    if 원판이 1개:
        이동 from 시작기둥 to 대상기둥

    if 원판이 2개 이상:
        #아래의 원판을 제외하고, 시작 기둥에서 보조 기둥으로 이동합니다.
        하노이탑(원판 -1, "시작기둥"에서 "보조기둥"으로 "대상기둥"을 활용해서)
        이동 from 시작기둥 to 대상기둥

        #아래의 원판을 제외하고, 보조 기둥에서 대상 기둥으로 이동합니다.
        하노이탑(덩어리 -1, "보조기둥"에서 "대상기둥"으로 "시작기둥"을 활용해서)

 

• 하노이 탑 문제는 재귀를 이용한 대표적인 알고리즘이다.
• 혼자서 해결해 보려했지만 알고리즘 구현이 쉽지 않아서 다음과 같이 힌트를 얻어서 코드를 작성했다.
• 시작, 대상, 보조 기둥의 순서를 바꾸어가면서 재귀함수를 호출을 하면 하노이 탑의 규칙대로 원판을 이동시킬 수 있다.

• N=3인 경우 원판의 움직임을 그려보면 다음과 같다.
• 출발기둥 -> 이동기둥 을 바꾸어가면서 재귀를 활용하면 이를 구현할 수 있다.
  • a->c 인 경우 hanoi(n-1 , a , c , b)
  • c->b 인 경우 hanoi( n-1 , c , b , a)
  • 원판이 1개 남게 되면 재귀를 멈추고 최종 원판만 목적지로 이동

---

구현코드 1

 메모리 초과

def move(n,a, b, c): # n : 원판개수 , a : 시작 기둥 , b : 대상 기둥 , c : 보조 기둥
    global count
    #원판이 한 개이면 바로 대상 기둥으로 이동 가능
    if n == 1:
        count += 1
        result.append([a,b])
    #원판이 두 개 이상인 경우 -> 보조 기둥을 거친다.
    else:
        count += 1
        move(n-1 ,a,c,b)
        result.append([a,b]) # 시작 -> 보조
        move(n-1 ,c,b,a)


n = int(input())
count = 0
result = []
move(n,1,3,2) #n개의 원판을 1번 기둥에서 3번 기둥으로 이동하는데 2번기둥을 활용

print(count)
for i in result:
    print(*i)

• 다음 코드는 정확한 답이 나오는 코드이다.
• 하지만 문제의 조건에서 메모리초과라는 문제가 발생한다.
• 원인은 count라는 변수를 count += 1을 통해서 재귀가 발생할 때마다 횟수를 체크하는 방식을 사용한 것이다.
• 메모리 조건을 작게 둔 것을 보아 본 문제에서는 이런 방법을 사용하면 안된다.
• 따라서 N이 증가함에 따라서 count의 개수 관계를 파악해보면
  • N=1 , cnt = 1
  • N=2 , cnt = 3
  • N=3 , cnt = 7
• 위에서 규칙을 구해보면 2^n - 1 이라는 규칙임을 알 수 있다.
• 위 규칙을 적용해 count를 구하게 되면 result 리스트 또한 사용하지 않고, 바로 print를 통해서 출력할 수 있어 메모리를 절약하게 된다.

---

구현코드 2

def move(n,a, b, c): # n : 원판개수 , a : 시작 기둥 , b : 대상 기둥 , c : 보조 기둥W
    #원판이 한 개이면 바로 대상 기둥으로 이동 가능
    if n == 1:
        print(a, b)
        return
    #원판이 두 개 이상인 경우 -> 보조 기둥을 거친다.
    
    if n <= 20:
        move(n-1 ,a,c,b)
        print(a, b)
        move(n-1 ,c,b,a)


n = int(input())
print(2**n - 1) # ★★★★
move(n,1,3,2) #n개의 원판을 1번 기둥에서 3번 기둥으로 이동하는데 2번기둥을 활용

• 위를 반영한 코드이다.
• 추가적으로 문제의 출력 조건에서 N<=20에 대해서만 출력하라는 조건을 하지 않으면 출력 초과가 발생하기에 조심해야하는 문제이다.

 

문제링크