하노이의 탑

 

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

프로그래머스

문제풀이

작은 순서부터 우선 이동할 수 있게끔 해야 하므로 재귀적인 방법으로 풀이가 가능하다.

 

• 원판은 항상 크기가 큰 순서부터 쌓아야 한다. 각 원판은 중간 기둥을 지나서 목표 위치에 도달해야 한다. 또한 n이 홀수라면 첫 이동시 1의 크기의 원판은 끝 기둥으로 이동해야 하며 짝수라면 중간 기둥으로 이동해야 한다.
• 재귀의 최대 깊이 즉 원소의 값이 가장 작은 값을 우선적으로 계산하기 위해 3개의 기둥 중 시작위치, 목표위치, 경유위치의 값을 바꿔 주면서 깊이 탐색을 해준다. 

| 은 각 수행 단계의 경계선, 굵음 표시는 시작위치, 굵음 표시는 목표위치,  0은 빈 공간, 0 이상의 숫자들은 원판의 크기라고 가정하자 n이 3일 때를 기준으로 시뮬레이션을 해본다면

 

1 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0  | 0 0 1

2 0 0 | 2 0 0 | 0 0 0 | 0 1 0 | 0 1 0 | 0 0 0 | 0 0 2  | 0 0 2

3 0 0 | 3 0 1 | 3 2 1 | 3 2 0 | 0 2 3 | 1 2 3 | 1 0 3  | 0 0 3 

위와 같이 7번의 과정을 수행하는 게 최적의 해가 될 것이다. 위의 과정을 재귀로 표현하면 아래와 같다.

def solution(n):
    answer = []

    def recursion(n, start, to, mid):
        if n == 1:
            return answer.append([start, to])
        else:
            recursion(n - 1, start, mid, to)
            answer.append([start, to])
            recursion(n - 1, mid, to, start)
        return answer

    return recursion(n, 1, 3, 2)