[Python] 백준, 11729(재귀)

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

재귀 알고리즘은 내가 배운 알고리즘들 중에서 가장 추상적인 알고리즘이다. 틀이 명확한 다른 알고리즘에 비해서 재귀는 깊이 들어갈수록 늪에 빠지는 느낌이 강하게 든다. 일일이 케이스를 분류하고 100프로 이해하려는 것보다 어느 정도 선에서 특수한 규칙까지만 확인하고 느낌대로 수정해나가는 게 더 효율적인 접근방식인 듯하다.

프로그래머스의 기초 강의와 알고리즘 도서로 간단히 복습은 했는데, 크게 와닿지는 않았다. 상향식 분석과 하향식 분석에 대한 참고 정도만 가져가면 좋을 듯하다. 추가하자면, 종결 조건에 대한 언급이 없으면 무한 재귀에 빠질 수 있으므로 유의하자는 내용도 챙기자.

하노이의 탑은 몇번 보기는 했지만, 자력으로 풀기에는 여전히 힘들게 느껴지는 문제다. 우선 아직도 경우의 수가 2**n-1이 나오는지 모르겠으며, 틀에 대한 이해 정도만 갖고 있기에 굉장히 찝찝하다. 맞은 사람의 풀이 중, 효율성을 높이고자 n = 2일때의 경우를 재귀에 포함시키지 않은 풀이가 있었는데 이게 위에서 언급한 특수한 규칙을 확인한다는 말과 가장 유사한 것 같다.

# PYTHON CODE

        n = int(input()) 
      

          
      
 def move(no, x, y): 
      

            answer = 0 
      

          
      

            if no > 1: 
      

                move(no - 1, x, 6 - x - y) 
      

          
      

            print(x, y) 
      

            answer += 1 
      

          
      

            if no > 1: 
      

                move(no - 1, 6 - x - y, y) 
      

          
      
 print(pow(2, n) - 1) 
      

        move(n, 1, 3)