백준 1914번 - 하노이 탑(Python)

컴공 자료구조 수업을 들어봤다면 한번쯤은 들어봤을 법한 문제인 하노이 탑 문제이다. 당시에 나는 C언어를 통해 재귀호출 방식을 사용하여 이 문제를 풀었는데, 원판의 개수가 지정되어 있지 않고 사용자의 입력에 따라 달라지기 때문에 이번 문제 풀이에서도 재귀 호출 방식을 통해 문제를 해결했다. 

문제에서 장대의 개수는 세 개로 고정되어 있고, 사용자가 입력한 개수만큼의 원판을 1번 장대에서 3번 장대까지 옮기는 데에 시행되는 횟수와 이동 과정을 출력하도록 구성되어 있다. 

 

재귀호출 예시 - 팩토리얼

재귀 함수는 자기 자신을 호출하는 함수를 일컫는데, 이 경우 함수 정의문 내에서 base 조건이 갖는 값을 이용하여 함수가 반복 시행됨에 따라 최종 값을 구해낸다. 

def Fact(n):
    if n == 1: # n이 1인 경우 1를 반환
        return 1
        
    # n이 1보다 큰 경우 
    return n * Fact(n-1)

위의 팩토리얼 함수에서 사용되는 재귀 함수 Fact(n)의 경우, Fact(1)의 값은 1이다.(1!=1)  

Fact(2), 즉 2! = 2 * 1(=1!) = 2 이고 

Fact(3), 3! = 3 * 2(=2!) = 6 에서 Fact(n)은 Fact(n-1) 값을 참고하여 값을 계산할 수 있기 때문에 Fact(n)의 값을 구하는 경우 Fact(1)의 값을 기본으로 하여 n까지의 숫자를 곱해 최종 Fact(n)의 값을 구해낼 수 있으므로 재귀 호출을 사용하는 것이 코드 상으로도 간단하다. 

(예시, 코드 출처: https://velog.io/@jewon119/01.%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-%EC%9E%AC%EA%B7%80-%ED%98%B8%EC%B6%9CRecursive-Call)

 

문제로 다시 돌아와서! 

그렇다면 하노이 탑 문제에서 문제 해결의 가장 기본이 되는 경우는 무엇일까? 

 

원판이 한 개인 경우(n=1)

바로 원판의 개수가 하나인 경우이다. 이때 하노이 탑의 출발점(1)에서 도착점(3)까지 한 번의 시행만 이루어지면 되기 때문에 이를 바탕으로 재귀 함수를 구성해야 한다. 

입력 1 -> 출력 1(1 3)

 

원판이 두 개인 경우(n=2)

그 다음으로 원판이 두 개인 경우, 위에 있는 원판을 먼저 중간(2)점에 옮겨둔 후, 아래에 있는 원판을 도착(3)점에 옮긴다. 그 후에 아래 원판 또한 도착(3)점에 위치시켜 세 번의 이동으로 마무리한다. 

입력 2 -> 출력 3(1 2, 1 3, 2 3)

 

원판이 세 개인 경우(n=3)

원판이 세 개인 경우, 총 일곱번의 시행이 이루어 지는데, 맨 아래 원판의 이동을 기점으로 나누어봤다. 하노이 탑에서 원판의 크기가 더 크면 작은 원판 위에 올라갈 수 없기 때문(조건)에 맨 아래 원판은 항상 다른 원판들이 위에서 사라진 후에만 이동할 수 있고, 도착점(3)에 가장 먼저 쌓여져야 한다. 그렇기 때문에 맨 아래 원판을 제외한 나머지 원판들을 출발점(1)에서 중간점(2)으로 모두 옮겨준 후에, 맨 아래 원판을 도착점(3)으로 옮기고, 마지막으로 나머지 원판들을 도착점(3)에 옮기는 과정으로 이동 과정을  크게 나눠볼 수 있다. 

입력 3 -> 출력 7(1 3, 1 2, 3 2, 1 3, 2 1, 2 3, 1 3)

 

def hanoi(n, from_p, mid_p, to_p): # 하노이 탑 함수(재귀 호출)

    if n==1: # base: 원판의 개수가 1개인 경우 
        print(from_p, to_p, sep = " ")
        
    else: # 원판의 개수가 2개 이상인 경우 
    
    	# 맨 아래 제외(n-1개) 원판을 중간 지점(mid_p)로 이동시킨다 
        hanoi(n-1, from_p, to_p, mid_p) 
        
        # 맨 아래 원판을 도착 지점(to_p)로 이동시킨다 
        hanoi(1, from_p, mid_p, to_p)
        
        # 중간 지점(mid_p)에 있는 원판들을 도착 지점(to_p)로 이동시킨다 
        hanoi(n-1, mid_p, from_p, to_p)
    
# 사용자 입력: 원판의 개수         
a = int(input())

# 원판 이동 횟수 
print(2**a-1)

# 조건 - 원판의 개수는 20개 이하일 때만 과정이 출력된다 
if(a<=20):
    hanoi(a, 1, 2, 3)

원판의 이동 횟수는 

n=1 ) 1 = 2 - 1

n=2 ) 3 = 2^2 - 1

n=3 ) 7 = 2^3 - 1 의 규칙성을 가지므로 

n 개의 원판이 출발점에서 도착점으로 이동할 때는 2^n - 1 번으로 규칙성을 가짐을 알 수 있었다. 

그림은... 제가 그린 기린 그림만도 못하므로 참고하는 데에만 써주시길 바라며...(과연 누가 하겠나 싶지만)