[프로그래머스 lv2] 하노이의 탑

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개의 원판을 x에서 y로 움직여야 하는 경우, 로직은 다음과 같다. 

1. n-1개의 원판을 x번 기둥에서 6-x-y번 기둥으로 옮긴다.
       (n이 1이 될 때까지, n이 1이 되는 경우 x번기둥에서 y번 기둥으로 바로 옮겨준다. )

2. n번째 원판을 x번 기둥에서 y번 기둥으로 옮긴다.

3. n-1개의 원판을 6-x-y번 기둥에서 3번 기둥으로 옮긴다. (n이 1이 될 때까지)

       (n이 1이 될 때까지, n이 1이 되는 경우 x번기둥에서 y번 기둥으로 바로 옮겨준다. )

 

 

 

코드 구현

 

def hanoi(n, answer, x, y):
    if n == 1:
        answer.append([x, y])
        return
    hanoi(n-1, answer, x, 6-x-y)
    answer.append([x, y])
    hanoi(n-1, answer, 6-x-y, y)

def solution(n):
    answer = []
    hanoi(n, answer, 1, 3)
    return answer

 

 

코드 구현시 재귀 함수의 원리

 

시간/공간 복잡도

 

O(2^n)

 

최적화 및 개선

 

따로 하지 않음

 

어려웠던 점

 

해당 문제의 코드는 직접 원판을 옮기면서 검증해봐야  재귀함수가 이해될 수 있다.  

아직까지 한번도 접해보지 않은 유형에 대해 재귀함수로 문제를 풀어보라하면 어려움을 겪는다. 

너무 어렵다 ㅠㅠ..

코드는 간단한데 원리에 대한 생각과 구현이 너무 어렵다.

 

https://vidkidz.tistory.com/649

하노이의 탑 (Tower of Hanoi)

 

해당 사이트에서 직접 하노이의 탑의 원판을 옮겨가면서 검증했다.