[재귀] 프로그래머스 - 하노이의 탑

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

 

문제 설명

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

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

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

제한사항

• n은 15이하의 자연수 입니다.

 

입출력 예

n	result
2	[ [1,2], [1,3], [2,3] ]

 

입출력 예 설명

입출력 예 #1
다음과 같이 옮길 수 있습니다.

 

 

 

 

문제 풀이

대표적인 재귀 문제 중에 하나인 하노이타워 문제이다. 사실 전에 알고리즘 수업을 수강할 때 하노이타워를 배우긴 했지만, 오히려 np 문제와 같은 더 난이도 있는 문제보다 하노이 문제가 어렵게 느껴졌다. 그 전까진 한 번도 제대로 이해해 본 적 없는 것 같은데, 이번 기회에 제대로 이해하게 되었다. 

 

큰 흐름은

가장 큰 원판을 목적지에 갖다 두기 위해서 그 앞의 n-1개를 중간 위치로 옮긴다

-> 가장 큰 원판을 목적지에 둔다

-> 중간 위치에 있던 n-1개를 목적지로 옮긴다

 

이렇게 흘러 간다. 이 과정을 재귀적으로 반복하면 된다. 

 

즉 원판이 세개라고 하면

1. 먼저 위의 2개를 중간 위치(2)로 옮긴다. 

• 여기서 시작점 = (1) , 중간위치 = (3), 목적지 = (2)
• 먼저 위의 1개를 중간 위치(3)로 옮긴다.
• 2번째 원판을 목적지(2)로 옮긴다.
• 중간 위치(3)에 있던 1번째 원판을 목적지(2)로 옮긴다. 

2. 3번째 원판(가장 큰 원판)을 목적지(3)로 옮긴다.

3. 중간 위치(2)에 있던 2개를 목적지로 옮긴다. 

• 여기서 시작점 = (2) , 중간위치 = (1), 목적지 = (3)
• 먼저 위의 1개를 중간 위치(1)로 옮긴다.
• 2번째 원판을 목적지(3)로 옮긴다.
• 중간 위치(1)에 있던 1번째 원판을 목적지(3)로 옮긴다. 

이러한 과정이 반복되는 것이다. 

 

 코드는 다음과 같다. 

answer = []

def hanoi_tower(n, start, mid, target):
    global answer
    if n == 1:
        answer += [[start, target]]
    else:
        hanoi_tower(n-1, start, target, mid)
        answer.append([start, target])
        hanoi_tower(n-1, mid, start, target)

def solution(n):
    hanoi_tower(n, 1, 2, 3)
    return answer