[파이썬]백준11729번 하노이탑 재귀함수로 풀기

백준11729번 문제는 하노이탑 이동 순서 문제입니다.

하노이탑 이동 문제는 대표적인 재귀함수로 풀기 쉬운 문제이며, 재귀함수를 이해하기에도 좋은 문제입니다.

자 그럼 여기서 하노이탑 문제란 뭐냐?

다들 이런식으로 생긴 장난감 본적 있을겁니다.

왼쪽처럼 생긴 모양을 오른쪽 모양으로 옮기는 문제이며, 여기서 작은 원판 위에는 큰 원판이 올 수 없습니다.

기본적인 하노이탑 이동 문제의 이동 규칙이며, 백준 알고리즘 11729 문제는 이 하노이탑에서 원판을 이동하는 순서와 전체 이동 횟수를 출력하는 문제입니다.

일단 파이썬으로 작성된 코드부터 보고 본격적으로 코드 및 문제 설명 들어갑니다

 

백준 11729 답안 파이썬 코드

def movement(n,f,e,t,Arr): #f에서 t로 이동한다 e는 비어있는 공간
    if n < 2: # 1개면 t로 이동한다고 출력하고 리턴(기저조건)
        Arr.append(str(f) + ' ' + str(t))
        return
    movement(n-1,f,t,e,Arr) #n-1개를 비어있는 곳으로 이동
    Arr.append(str(f) + ' ' + str(t))
    movement(n-1,e,f,t,Arr) #n-1개를 최종 f로 이동
N = int(input())
Arr = []
movement(N,1,2,3,Arr)
print(len(Arr))
for i in Arr:
    print(i)

가장 기초적인 파이썬 문법만을 사용해서 풀어본 답안입니다.

지금부터 코드를 보면서 백준 11729 하노이탑 이동 문제 해석 들어갑니다.

 

1. 입력
   • 백준 알고리즘 홈페이지에서 확인하셨겠지만 입력으로는 1~20 사이의 하나의 정수가 입력됩니다
   • 파이썬 코드로 int로 입력받을 수 있고 N에다가 정수형으로 저장하게 됩니다

     N = int(input())​

2. 변수선언
   
   • 입력받기 위한 정수형 변수인 N과 함께 최종적으로 출력을 위한 리스트형 변수인 Arr를 선언해줍니다
   • 코드에서 [] 으로 초기화 해준 이유는 Arr 변수를 리스트라고 정해두기 위해서입니다.

     Arr = []​

3. movement 함수 호출
   1. movement라는 함수를 호출해줍니다
   2. movement 함수는 앞에서 선언한 것처럼 4개의 정수형 매개변수와 1개의 출력용 리스트 매개변수를 사용합니다

      movement(N,1,2,3,Arr)

   3. movement 함수에서 매개변수로 사용되는 숫자의 의미를 적어보겠습니다.

      movement(n,f,e,t,Arr)​

      1. n : 백준 알고리즘 11729에 나온 것과 같이 최초로 입력받은 하노이탑의 원판 개수입니다.
      2. f : from으로 원판이 어디서 이동할지 입력해주는 값입니다 최초 호출의 경우 1번 기둥에서 3번 기둥으로 이동하기 때문에 1이 입력됩니다.
      3. e : empty로 사용하지 않는 기둥의 번호입니다. 최초로 함수 호출하는 경우 위에 언급한 것과 같이 1에서 3으로 이동하기 때문에 2가 지정됩니다.
      4. t : to로 이동할 기둥의 번호입니다 3번 기둥으로 옮겨야하기 때문에 3이 됩니다.
      5. Arr: 출력을 하기 위한 리스트입니다. 문제를 보시면 이동이 끝난 후 횟수를 출력하는게 아니라 횟수를 출력하고 이동 경로를 출력하게 됩니다. 그렇기 때문에 리스트를 사용했고 만약 그 반대거나 횟수를 출력할 필요가 없다면 바로 프린트 구문을 사용할 수 있습니다.
         • 추가적으로 하노이 탑의 경우 간단한 수학공식으로 횟수를 구할 수 있기 때문에 횟수를 구해서 출력하고 리스트를 사용하지 않을 수 있습니다.
   4. 출력
      • 출력은 먼저 Arr 변수의 입력된 개수를 출력하고 반복문을 통해 입력된 내용을 한줄씩 출력합니다

        print(len(Arr))
        for i in Arr:
            print(i)​

   5. movement 함수 분석

      def movement(n,f,e,t,Arr): #f에서 t로 이동한다 e는 비어있는 공간
          if n < 2: # 1개면 t로 이동한다고 출력하고 리턴(기저조건)
              Arr.append(str(f) + ' ' + str(t))
              return
          movement(n-1,f,t,e,Arr) #n-1개를 비어있는 곳으로 이동
          Arr.append(str(f) + ' ' + str(t))
          movement(n-1,e,f,t,Arr) #n-1개를 최종 f로 이동​

       
      1. movement 함수는 제목에서와 같이 재귀함수로 구현했습니다. 재귀함수에 대한 자세한 설명은 마지막에 링크로 첨부하겠습니다.
      2. 매개변수는 앞서 movement 함수 호출에서 설명했으니 넘어가도록 하겠습니다.
      3. 먼저 재귀함수의 가장 중요한 요소중 하나인 종료조건(기저조건)을 입력해줍니다. n이 1인 경우 즉, 원판이 하나인 경우 from에서 to로 한번만 이동하면 되기 때문에 간단하게 이동을 추가해줍니다.
      4. 그 외의 경우가 본격적으로 재귀를 사용하게 됩니다.
         1. 원판이 두개인 경우부터 보겠습니다
            1. 1번(가장 작은 원판)을 1번 기둥에서 2번 기둥으로 옮겨줍니다.(2번 기둥을 3번 기둥으로 옮기기 위함.) 
            2. 2번 기둥을 3번 기둥으로 옮기고 2번 기둥에 있는 1번 기둥을 3번 기둥으로 옮겨주게 됩니다.
            3. 총 3번의 이동이 발생하고 1 2(1에서 2), 1 3(1에서 3), 2 3(2에서 3) 으로 출력되겠죠
         2. 세개로 가보겠습니다
            1. 3번을 세번째 기둥으로 옮기기 위해서는 위에 두개 즉 n-1개의 원판을 empty 즉, 2번 원판으로 갖다놔야합니다. 그렇기 때문에 n-1을 f에서 e로 옮기고 비어야 하는 기둥은 t가 되기 때문에 아래와 같이 재귀를 호출합니다.

                   movement(n-1,f,t,e,Arr) #n-1개를 비어있는 곳으로 이동​

            2. 이제 t 기둥이 비어있고 f 기둥에는 가장 큰 원판이 남아있겠죠? f 기둥에 있는 가장 큰 원판을 t로 이동해줍니다.

                   Arr.append(str(f) + ' ' + str(t))​

            3. 다음으로 최초 e인 2번 기둥으로 옮겨져있던 원판을 최초 t인 3번 기둥으로 옮겨줘야합니다. 따라서 n-1개의 기둥을 e에서 t로 옮겨주는 재귀를 호출합니다.

                   movement(n-1,e,f,t,Arr) #n-1개를 최종 f로 이동​

            4. 정리해보면 원판이 3개인 경우 위에 2개를 남는 기둥으로 옮긴 후 비어있는 3번째 기둥에 원판을 넣고 비어있는 기둥으로 옮겨졌던 원판을 최종 목적지로 이동하는 행위를 반복하게 됩니다.
   6. 전체 정리
      • 전체적으로 보면 원판이 3개인 경우 2개의 원판을 이동하는걸 두번 반복하면서 이동이 가능하고 2개인 경우 1개의 원판으로 나누어서 분할정복을 하게 됩니다. 여기서 재귀함수의 조건 중 하나인 분할정복이 사용됩니다.
      • 백준 11729 하노이 탑 문제는 대표적인 재귀함수 문제로 반복문으로 풀 수 있지만 재귀함수를 사용하는 편이 훨씬 코드가 간편하고 재귀함수를 이해만 한다면 훨씬 쉽게 풀 수 있습니다.
      • 하노이탑 문제의 이동 횟수만 구하는 경우 간단한 수식으로 구할 수 있고, 그런 경우 Arr에 넣지 않고 print 문으로 바로 출력해주어도 됩니다.
      • 재귀함수의 경우 너무 호출 횟수가 많아지면 스택 오버플로에 빠질 수 있지만, 백준 11729 문제의 경우 원판의 갯수가 20개 이하로 제한되어있기에 여기서는 문제가 되지 않습니다.