백준 11729번 - 하노이 탑 이동 순서

N = 3 에서 N = 4, 5정도까지 직접 옮겨보면 대충 어느 부분에서 재귀를 사용해야 할 지 감이 온다. N = k 일 때

k-1개의 블럭을 2번으로 옮긴 뒤 k번째(가장 큰 블럭) 블럭을 3번으로 옮기고 k-1개의 블럭들을 (3번에 k번째 블럭이 없다고 생각하고) 3번으로 옮겨주면 된다. k-1개의 블럭들을 옮기는 작업이 반복이 되기 때문에, 이 부분을 재귀함수를 이용해서 구현하면 되겠다. 주의해야 할 점은 k의 짝홀수 여부에 따라 옮기는 곳이 다르다는 점이다.

예를 들면, k = 4일 때는 3개를 2로 옮기는데, 3개를 2로 옮길 때는 2개를 2가 아닌 3으로 옮겨야 한다. 그러므로 단순히 Hanoi(N-1, 1, 2)로 쓰는 것이 아니라, 변수를 사용해서 재귀가 호출 될 때 목적지가 달라지게 해야된다. 

 

Hanoi 함수는 N개의 블럭과 어디에서 어디로 옮길 것인지에 대한 변수 _from과 _to 를 받는다. 

크게 볼 때 우리는 N개의 블럭을 1에서 3으로 이동시킬 것이기 때문에, 메인 함수에서 호출은 Hanoi(N, 1, 3)이다.

N이 1씩 줄면서 1이 될 때 종료해줘야하기 때문에 num = 1이면 1을 옮겨주는 과정을 출력해준다.

N - 1개의 블럭을 모두 2로 옮기고 나면 1에 있는 가장 큰 블럭을 3으로 옮겨줘야하기 때문에, _from에서 _to를 출력해준다.

그리고 다시 2에서 3으로 옮겨야하기 때문에, 첫번째로 호출되는 함수에서 _from과 _to의 자리만 바꿔주면 된다.

##함수 선언 부분
def Hanoi(num, _from, _to):
    if num == 1:
        print(_from, _to)
    else:
        Hanoi(num - 1, _from, 6 - _from - _to) #num - 1개를 1에서 2로 이동
        print(_from, _to) #제일 큰 판을 3으로 이동
        Hanoi(num - 1, 6 - _from - _to, _to) #2에서 3으로 이동
##변수 선언 부분
N = 0

##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    print(2**N - 1)
    Hanoi(N, 1, 3)

자료구조 수업 때 했었는데, 많이 까먹어서 그런지 꽤 어려웠다. 노트에 경우 하나하나 옮기면서 규칙을 찾았지만, 짝홀수에 따라 처음 1 을 옮기는 위치가 다르다는 점에서 헤맸던 것 같다. 하나하나 규칙을 찾기보다는 추상적으로 몇개를 어디에서 어디로 옮기는 지를 구현하는 것이 중요한 문제였다.