[ 프로그래머스 해설 ] ( python ) 하노이의 탑

 

📚 하노이의 탑

 

 

 

문제 설명

 

하노이 탑(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
다음과 같이 옮길 수 있습니다.

 

 

 

 

✍ 접근

• 처음에는 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)

 

 

 

 

⭐ 배움

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