[프로그래머스 Lv.2] 하노이의 탑 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

풀이

그 유명한 하노이의 탑을 풀기 위한 방법을 순서대로 배열에 넣어 출력하면 되는 문제이다.

재귀를 활용해 풀이하면 되는 문제인데, 재귀 문제가 모두 그렇듯이 재귀 과정에서 어떤 연산을 거쳐야 하는지 정의해야 하고, 종료 조건도 정의해야 한다.

우선 재귀 과정을 거치면서 어떤 연산을 거쳐야 하는지 고민을 해봐야 한다. 연산에서의 규칙을 찾을 수 있게 "/"로 단계를 분리해서 적어보면 아래와 같다.

• 2개일 때 [1,2] / [1,3] / [2,3]
• 3개일 때 [1,3], [1,2], [3,2] / [1,3] / [2,1], [2,3], [1,3]
• 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-1개의 원판들을 3번을 거쳐 2번으로 모두 옮기고, 두 번째 단계에서는 가장 큰 원판 하나를 3번으로 옮기고, 마지막 세 번째 단계에서는 n-1개를 1번을 거쳐 다시 3번으로 모두 옮기면 된다. (물론 옮길 원판이 하나인 경우에는 최소 횟수를 계산하는 것이므로 중간 위치를 거치지 않고 바로 이동)

 

좀 더 자세하게 3개일 때를 기준으로 설명해 보겠다. 앞서 말한 기준대로 3단계로 나누면 아래와 같다.

1. 2개의 원판을 3번을 거쳐 2번으로 모두 이동
2. 가장 큰 하나의 원판을 3으로 이동
3. 2개의 원판을 1번을 거쳐 3번으로 모두 이동

다시 1단계인 "2개의 원판을 3번을 거쳐 2번으로 모두 이동"을 아래와 같이 분리할 수 있다.

1개의 원판을 3번으로 이동 / 가장 큰 하나의 원판을 2번으로 이동 / 남은 1개의 원판을 3번에서 2번으로 이동

 

2단계인 "가장 큰 하나의 원판을 3으로 이동"은 단순히 한 개의 원판을 현 위치에서 3으로 이동하면 되는 것이기 때문에 더 이상 분리를 할 수가 없다. 따라서 재귀 종료 조건은 옮길 원판이 하나일 때이다.

 

마지막으로 3단계인 "2개의 원판을 1번을 거쳐 3번으로 모두 이동"을 아래와 같이 나누어보자.

1개의 원판을 1번으로 이동 / 가장 큰 하나의 원판을 3번으로 이동 / 남은 1개의 원판을 1번에서 3번으로 이동

 

이제 위에서 나누어본 모든 과정을 정리하면 아래와 같다.

1. 1개의 원판을 3번으로 이동 / 가장 큰 하나의 원판을 2번으로 이동 / 남은 1개의 원판을 3번에서 2번으로 이동
2. 가장 큰 하나의 원판을 3으로 이동
3. 1개의 원판을 1번으로 이동 / 가장 큰 하나의 원판을 3번으로 이동 / 남은 1개의 원판을 1번에서 3번으로 이동

이제 이 과정의 이동하는 과정을 번호로 직접 적어보면 아까 위에서 알아보았던 [1,3], [1,2], [3,2] / [1,3] / [2,1], [2,3], [1,3]와 동일하다.

 

즉, 위의 긴 증명 과정을 통해 우리는 n개의 원판을 옮기는 하노이의 탑 문제를 아래와 같이 해결할 수 있다. (단, 출발지는 1번, 중간 위치는 2번, 목적지는 3번이라고 가정한다.)

1. n-1개를 목적지(3번)를 거쳐서 중간 위치(2번)로 옮긴다.
2. 가장 큰 원판을 목적지(3번)로 옮긴다.
3. 중간 위치(2번)에 존재하는 n-1개의 원판을 출발지(1번)를 거쳐 목적지(3번)로 옮긴다. 
4. 각 단계를 또다시 같은 방식을 사용해 단계를 분리하여 1개의 원판만을 옮길 때까지 재귀적으로 반복한다.

위의 과정을 구현하면 문제 해결이 완료된다.

def solution(n):
    answer = []
    return hanoi(n, 1, 2, 3, answer) # 1번에서 출발하여 2번을 거쳐 3번으로 모든 원판을 옮기는 것이 하노이의 탑 문제의 해결 방법
    
    
    
def hanoi(n, start, mid, end, answer):   
    if n == 1: # 종료 조건
        answer.append([start, end]) # 단순히 원판을 출발지에서 목적지로 옮기기만 하면 됨
        return answer
        
    hanoi(n-1, start, end, mid, answer) # n-1개의 원판을 출발지에서 목적지를 거쳐 중간 위치로 이동
    answer.append([start, end]) # 가장 큰 원판을 출발지에서 목적지로 이동
    hanoi(n-1, mid, start, end, answer) # 나머지 n-1개의 원판을 중간 위치에서 출발지를 거쳐 목적지로 이동
    return answer

코드를 실제로 보면 생각보다 매우 간단한 것을 확인할 수 있다. 이것이 재귀 문제의 특징이다. 해결방법만 잘 알아낸다면 코드 작성은 쉽게 할 수 있다.