알고리즘 코드카타 123- 하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

문제 설명
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항
n은 15이하의 자연수 입니다.

 

 

하노이의 탑 게임을 구현하는 알고리즘, 이번 문제를 풀면서 알게된 사실이지만 재귀함수를 공부하는데 있어서 유명한 예제라고 한다.

 

# n = 1 -> [[1, 3]]
# n = 2 -> [[1, 2], [1, 3], [2, 3]]
# n = 3 -> [[1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]]
# n = 4 -> [[1, 2], [1, 3], [2, 3], [1, 2], [3, 1], [3, 2], [1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [2, 3], [1, 2], [1, 3], [2, 3]]

 

재귀함수를 사용해야한다는 것은 알아버렸으므로 아쉬운대로 규칙을 찾아보자.

원판이 하나일때는 당연히 출발지점의 원판을 도착지점으로 옮겨주면 된다.

원판이 두개인 경우를 살펴보자. 두개의 원판이 출발지점에서 도착지점으로 이동해야하는데 그 과정에서 하나의 원판이 경유지를 통과해야한다. 그리고 하나 남은 원판은 출발지점에서 도착지점으로 이동하고 마지막으로 경유지에 남아있는 원판이 도착지점으로 이동한다.

원판이 세개인 경우에도 논리는 같다. 세개의 원판이 출발지점에서 도착지점으로 이동을 해야하고 먼저 두개의 원판이 경유지에 도착해야한다. 그리고 출발지에 남아있는 원판 하나가 도착지점으로 이동하고 경유지에 있는 원판두개가 도착지점으로 이동한다. 이때, 두개의 원판을 이동시킬때, 원판이 두개인 경우가 그대로 반복된다. 즉, 출발지와 경유지만 달라질 뿐, 함수의 작동 자체는 동일하게 일어난다는 것이다.

 

따라서 하노이의 탑의 작동방식을 요약하면 다음과 같다

• n개의 원판을 출발지에서 도착지로 이동시킨다.
  • n-1개의 원판을 출발지에서 경유지로 이동시킨다.
  • ......
    • 1개의 원판을 출발지에서 도착지로 이동시킨다.
  • ......
  • n-1개의 원판을 경유지에서 도착지로 이동시킨다.

 

이것을 파이썬의 코드로 구현해보자.

 

def hanoi(n, start=1, to=3, via=2):
    result = []
    if n == 1:
        return [[start, to]]
    else:
#        n-1개 출발지 -> 경유지 이동
#        1개 이동
#        n-1개 경유지 -> 도착지 이동
    return result

 

출발지, 도착지, 경유지를 각각 start, to, via로 정의하고 기본값은 1, 3, 2로 한다. 원판의 전체 이동은 항상 1번에서 3번으로 이루어지고 그 과정에서 경유할 수 있는 곳은 2번밖에 없기 때문이다.

 

남은 원판이 하나인 경우 경유지를 거쳐갈 필요가 없으므로 현재의 출발지점에서 도착지점으로 원판을 이동시킨다.

남은 원판이 여러개인 경우 하노이의 탑을 구현하기 위한 로직을 작성한다.

 

# def hanoi(n, start=1, to=3, via=2):
#     result = []
#     if n == 1:
#         return [[start, to]]
#     else:
        result.extend(hanoi(n-1, start, via, to))
        result.append([start, to])
        result.extend(hanoi(n-1, via, to, start))
#     return result

 

가장먼저

• n-1개의 원판을 출발지에서 경유지로 이동시킨다.

라는 부분을 작성한다. 원판의 갯수를 조정하고 출발지에서 경유지로 도착해야하므로 도착지는 경유지가 되며 이동을 위해서는 남아있는 도착지를 경유하는 수 밖에 없다.

 

다음으로

• 1개의 원판을 출발지에서 도착지로 이동시킨다.

를 작성한다. 단순하게 현재 지정되어있는 출발지에서 도착지로 이동하면 된다. 재귀함수 내부에서 작동한 경우, 출발지와 도착지가 알맞게 변경되어있기 때문에 올바르게 작동한다.

 

마지막으로

• n-1개의 원판을 경유지에서 도착지로 이동시킨다.

를 작성한다. 첫 부분에서 이동한 원판 n-1개는 모두 경유지에 있는 상태이므로 경유지를 출발지로 하고 도착지점으로 이동시킨다. 이과정에서 경유지로 사용할 수 있는 기둥은 최초의 출발지밖에 없으므로 그곳을 경유한다.

 

위의 재귀함수는 반복되면서 출발지와 도착지, 그리고 경유지를 반영하여 원판을 필요한 곳으로 이동시킨다.

 

따라서 최종 코드는 다음과 같다.

 

def solution(n, start=1, to=3, via=2):
    result = []
    if n == 1:
        return [[start, to]]
    else:
        result.extend(solution(n-1, start, via, to))
        result.append([start, to])
        result.extend(solution(n-1, via, to, start))
    return result

(프로그래머스 제출을 위해서 함수의 이름만 수정한 상태)

 

완료!

 

재귀함수에 대한 부족한 개념을 보충할 수 있는 문제였다.

쉽지 않기도 했지만 작동원리를 파악할 수 있었다.