하노이 탑에서 원판을 옮기는 과정을 2차원 배열에 [출발 기둥, 도착 기둥]을 처음부터 끝까지 기록해서 반환하는 문제
기둥은 3개
큰 원판은 밑에 작은 원판은 위에 존재해야하는 규칙이 있음
문제 설명
하노이 탑TowerofHanoi은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
제한사항
n은 15이하의 자연수 입니다.
https://school.programmers.co.kr/learn/courses/30/lessons/12946
원판 1개 -> [[1,3]]
원판 2개 -> [[1,2],[1,3],[2,3]]
위의 과정을 계속 반복하면 n개의 원판을 옮길 수 있다.
주어진 원판의 개수가 홀수이면 맨 위에 있는 원판을 최종 목적지로 옮기고,
짝수이면 원판이 최종 목적지가 아닌 다른 기둥으로 옮겨야한다.
하나씩 하나씩 차근차근 하면 풀리는 문제인데, 실제 하노이 탑을 가지고 노는 것도 재밌다.
처음 출발지점 s = 1, 도착 지점 e = 3으로 세팅한다. 남는 기둥은 a라고 하자.
n이 홀수 일때는 이대로 진행, 짝수 일 때는 e와 a가 바뀌어야 한다.
그래서 아래 코드를 보면 move 함수에 n-1 인 경우, e와 a의 파라미터 위치를 바꿔 대입했다.
n개의 원판이 주어진 경우
n-1개의 원판을 2번 기둥에 옮긴다. 이 과정이 move함수 내에서 첫번째로 move함수가 recurrent 되는 내용이다.
그리고는 1번 기둥에 있는 마지막 n번째 원판을 3번 기둥으로 옮겨야한다. 이건 recurrent되는 두 move함수 사이에 있는 append 매소드가 사용되는 내용이다.
두번째 move함수가 재귀되는 부분은 2번 기둥으로 옮겨진 n-1개의 원판이 3번 기둥으로 옮겨가는 과정이다.
실제로는 재귀 과정이 계속 일어나서 위에서 말한 것처럼 원판을 1개, 2개가지고 옮기는 과정을 n개의 원판을 모두 옮길 때까지 반복하는 함수이다.
def move(s,e,a,n,li):
if n == 1:
li.append([s,e])
return
move(s,a,e,n-1,li)
li.append([s,e])
move(a,e,s,n-1,li)
def solution(n):
li = []
move(1,3,2,n,li)
return li
아래 코드는 위 코드와 원리는 같지만 더 짧습니다.
def move(s,e,a,n):
if n == 0:
return []
return move(s,a,e,n-1) + [[s,e]] + move(a,e,s,n-1)
def solution(n):
return move(1,3,2,n)
입출력 예
n | result |
2 | [ [1,2], [1,3], [2,3] ] |




'IT > Python' 카테고리의 다른 글
[백준] 26005번 나뭇잎 학회 [Python] 0 | 2023.08.28 |
---|---|
[백준] 28466번 볼링공 찾아주기 [Python] 0 | 2023.08.28 |
[백준] 3060번 욕심쟁이 돼지 [Python] - 등비수열 0 | 2023.08.24 |
[백준] 14494번 다이나믹이 뭐예요? [Python] - 다이나믹 0 | 2023.08.24 |