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

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

11729번: 하노이 탑 이동 순서

 

 

이 문제는 재귀 알고리즘의 대표적인 문제이다.

개인적으로 재귀에 가장 취약해서 못풀었었고, 다른 사람의 풀이코드를 봐도 이해하는 것이 힘들었다.

재귀는 백트래킹, DFS 등 알고리즘에서 자주 사용되니 반드시 이해하고 넘어가야한다.

 

재귀는 2가지 조건을 반드시 갖추어야 정상적인 동작을 할 수 있다.

1. 종료조건을 반드시 갖출 것

2. 자기 자신을 호출하되, 함수를 반복할수록 종료조건과 가까워져함

 

하노이탑의 규칙을 알고 있었음에도 풀이하지 못하였기에 유튜브 영상을 참고했다.

https://www.youtube.com/watch?v=FYCGV6F1NuY 

두고두고 복습할 것

 

해당 문제를 풀기 위해서는 하노이탑의 규칙을 알아야한다.

한 번에 하나의 원반을 옮기되, 작은 원반 위에 큰 원반을 놓을 수 없다.

위의 규칙을 생각해보면

편의상 A를 출발지, B를 보조지, C를 도착지로 두자.

A에 3개의 원반이 있다고 할 때, A의 원반 3개를 모두 C에 옮기려고 한다.

 

그럼 맨 마지막 원반을 제외한 2개의 원반을 모두 보조인 B에 옮겨야 A의 맨 마지막 원반을 목표지점인 C로 옮길 수 있다.

마지막 원반 위의 2개의 원반이 B로 이동했다고 치고, A의 맨 마지막 원반도 C로 이동했다고 치자.

(즉, A는 텅 비고 / B에는 원반 2개 / C에는 원반 1개가 있는 상태)

 

그럼 B의 2개의 원반 중 맨 마지막 원반을 제외한 하나의 원반이 A로 가야되고, B의 맨 마지막 원반은 C로 가야한다.

이 때, A가 보조역할을 하게 되며 B가 출발지가 된다.

(A에 원반 1개 / B에 0개 / C에 2개가 있는 상태)

 

마지막으로 A에 있는 원반 하나를 C로 옮겨주면 된다.

 

이를 통하여 하노이탑을 이동시키기 위해서는 출발지에서 보조지를 통해 도착지로 원반을 이동시킬건데, 원반을 이동시키기 위해서는 출발지의 맨 마지막 원반을 제외한 N-1개의 원반이 보조지로 이동한 후 맨 마지막 원반을 목적지에 두고, 나머지  N-1개의 원반을 목적지로 이동시키면 끝이난다. 이는 출발지와 목적지를 바꾸어가면서 & 원반의 갯수를 1씩 줄이면서 수행될 수 있다.

 

위의 이러한 규칙들을 가지고 재귀함수로 만들어보자.

결국 목표지점인 C로 원반을 옮기는 경우는 밑줄 친 경우인 출발지에 원반이 하나만 있을 경우이다.

이를 재귀함수의 종료조건으로 하면 된다.

 

위의 알고리즘을 보면 첫 번째와 두 번째 모두 출발지와 보조지가 바뀌었다는 차이만 있을 뿐 규칙은 동일하다.

따라서, 계속 재귀함수를 호출하되, 맨 마지막 원반을 제외하고 (원반의 수를 하나 줄인 상태에서) 나머지를 보조지로 옮긴 후, 다시 도착지로 옮기면 된다. 다시 도착지로 옮기기 위해서는 다시 보조지를 활용해야될 것이며, 규칙은 위에서 설명한 것과 동일하다.

 

이러한 알고리즘을 코드로 표현하면 다음과 같다.

 

def hanoi(n, a, b, c):  # a, b, c는 출발지, 보조지, 도착지를 의미
    if n == 1:  # 종료조건
        print(a, c)  # 출발지의 맨 마지막 원반을 도착지로 이동
        return
    else:
        hanoi(n - 1, a, c, b)  # 맨 마지막 원반을 제외한 n-1개의 원반을 도착지를 이용하여 보조지로 이동시킴(보조지가 도착지가 되어 다음 함수 호출때는 출발지가 됨)
        print(a, c)  # 출발지의 맨 마지막 원반을 도착지로 이동
        hanoi(n - 1, b, a, c)  # 맨 마지막 원반을 제외한 n-1개의 원반을 도착지로 이동시킴 (출발지:b, 보조지: a)


n = int(input())
print(2 ** n - 1)  # 공식이므로 암기할 것
hanoi(n, 1, 2, 3)

중간에 hanoi(n - 1, a, c, b) 다시 하노이 함수를 재귀 호출하는 것을 볼 수 있다.

이 때는 출발지 a의 n-1개의 원반을 도착지를 보조지로 활용하여 목적지인 b로 두는 하노이 함수이며, 이 함수는 다시 목적지인 b로 가기 위해 함수를 호출할 것이다.

 

사실 나중에 혼자 풀라고 하면 못 풀듯.. 어려웡..

복습 빡시게 ㄱㄱ

 

 

요건 하노이탑의 n개의 원반을 옮길 때 필요한 이동횟수 공식

그냥 외울 것