📚 하노이의 탑

문제 설명

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

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

하노이 탑의 세 개의 기둥을 왼쪽 부터 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
다음과 같이 옮길 수 있습니다.

✍ 접근

처음에는 stack을 이용해볼까 고민을 했다.(실패)
재귀를 돌면서 풀어야겠다는 생각을 했다.
하지만 어떻게? 에서 고민이 많았다.
재귀 + 약간의 dp적 사고가 필요하다.

정답코드

// ✨ 재귀 돌기
def hanoi (start,mid,end,n):
    if n == 1:
        answer.append([start,end])
        return
    hanoi(start,end,mid,n-1)
    hanoi(start,mid,end,1)
    hanoi(mid,start,end,n-1)

// ✨ 기본 코드
def solution(n):
    global answer
    answer = []
    hanoi(1,2,3,n)
    return (answer)

해설

기본 코드

원판이 움직이는 시작지점(start)와 끝 지점(end)를 배열로 만들어 담아줄 answer 배열을 만든다 (전역 변수로 이용하기 위해 global을 선언해준다)
첫 번째 탑에서 세 번째 탑으로 옮기는 것이기 때문에, 중간지점 mid(2)를 포함해서 hanoi 재귀함수에 집어넣어준다

재귀 돌기

dp적으로 생각해보자
- 만약 원판이 1개라면 ? => start -> end 한 번만 옮기면 된다
- 원판이 2개라면 ? => start-> mid // start -> end // mid -> end로 옮기면 된다
- 이 말은, end(타겟 지점)으로 옮기기 위해서는 원판이 몇 개가 쌓여있든 그 중 맨 마지막(가장 큰)원판이 먼저 end지점으로 옮겨가야 한다는 것.
- 그 전 원판들은 다 mid에 있어야 한다는 것이다.
- 그러면 다시 생각해보면.. 그 전 원판들이 다 mid에 가있으려면..? 처음 start지점의 두번째로 큰 원판이 mid지점의 맨 밑으로 가야 한다는 것
- => 3에 가장 큰 원판을 옮기고 / 2에 남은 원판들을 다 옮긴다
- => 2에 두번째로 큰 원판을 옮기고(1에는 가장 큰 원판이 남아있다 / 3에 남은 원판들을 다 옮긴다
- 를 반복해야 한다.
따라서 n이 1이 남게 되면(탑에 남은 원판이 하나라면) 그 원판이 옮겨가야 할 곳을 [start, end]로 만들어 answer에 넣어준다
그리고 재귀를 돌린다
- hanoi는 (시작 지점, 중간 거점, 끝 지점, 옮겨야 할 원판의 개수)를 변수로 받는다
- 시작 지점에 있던 원판 중 n-1개의 원판(맨 마지막 원판은 남겨둬야 하니)를 mid로 옮겨야 한다 => hanoi(start,end,mid,n-1)
- n-1개가 다 mid로 옮겨졌으면 마지막 하나의 원판을 end로 옮긴다 => hanoi(start,mid,end,1)
- 그리고 다시 중간지점에서 끝 지점으로 n-1개의 원판을 옮겨야 한다 => hanoi(mid,start,end,n-1)

⭐ 배움

재귀에 대한 이해를 필요로 하는 문제였다.
다시 한 번 풀어봐야지

저작자표시