백준 11729 풀이 (하노이탑)

오우 아주 쒯같지만 좋다고 느낀 문제였다. 계속 재귀에 대해서 벽을 느끼고 있었는데 재귀의 동작방식을 너무나 잘 공부할 수 있었다.

하노이탑 알고리즘을 보다 보니 너무 좋은 글을 써주신 블로거분이 있어서 참고하면 좋을거 같다.

(shoark7.github.io/programming/algorithm/tower-of-hanoi)

 

규칙은 쉬우나 문제는 법칙을 찾는게 어렵다는 것이다. 

그래서 3을 기준으로 어떻게 옮기는지 보면 몇가지 방식으로 규칙을 찾을수 있다.

완벽히 이해한게 아니라 설명이 어려운데.....

 

1. 3을 A->C로 옮기는 경우

2. 1,2를 A->B로 옮겨야한다.(2를 A->B로 옮기는 재귀함수)

3. 3을 A->C로 옮겨야한다.(1개만 옮겨도 되기 때문에 재귀가 필요없다.)

4. 1,2를 다시 B->C로 옮겨야한다.(2를 B->C로 옮기는 재귀함수)

끝!

 

즉 어떤 N을 옮겨야 한다면 N-1재귀함수를 2번 다른 방향으로 실행시키고, 나머지 가장큰 원반을 C로 옮기는 작업을 진행해주면 된다.

또한 재귀함수가 실행되면 2번과 3번에서 서로다른 방향으로 움직이기 때문에 기둥의 데이터를 재귀함수에서 전부 가지고 있어야한다.

따라서 재귀함수에 필요한 파라미터는 A,B,C가 모두 들어가야하는 것이다.

n = int(input())

def move(start, to):
    print(str(start)+" "+str(to))

def ha(n,start,to,via):
    if n == 1:
        return move(start,to)
    ha(n-1,start,via,to)
    move(start,to)
    ha(n-1,via,to,start)
print(2**n-1)
ha(n,"1","3","2")

어려웠지만 규칙을 발견한다면 코드는 간결해진다는게 너무 신기하다.