[1일 1문] 하노이의 탑

Sol Lee·2024년 2월 22일

문제

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

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

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

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

n은 15이하의 자연수 입니다.
출력 예시 n = 2, retult = [ [1,2], [1,3], [2,3] ]

나의 풀이

시간내에 못 풀었다. 🙃

다른 사람 풀이

질문하기에서 힌트를 봄

다른 사람이 올려놓은 예시


1
[1,3]

2
[1, 2], 

[1, 3], [2, 3]

3
[1, 3], 

[1, 2], [3, 2], 

[1, 3], [2, 1], [2, 3], [1, 3]

4
[1, 2], 

[1, 3], [2, 3], 

[1, 2], [3, 1], [3, 2], [1, 2], 

[1, 3], [2, 3], [2, 1], [3, 1], [2, 3], [1, 2], [1, 3], [2, 3]

5
[1, 3], 

[1, 2], [3, 2], 

[1, 3], [2, 1], [2, 3], [1, 3], 

[1, 2], [3, 2], [3, 1], [2, 1], [3, 2], [1, 3], [1, 2], [3, 2], 

[1, 3], [2, 1], [2, 3], [1, 3], [2, 1], [3, 2], [3, 1], [2, 1], [2, 3], [1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]

6
[1, 2], 

[1, 3], [2, 3], 

[1, 2], [3, 1], [3, 2], [1, 2], 

[1, 3], [2, 3], [2, 1], [3, 1], [2, 3], [1, 2], [1, 3], [2, 3], 

[1, 2], [3, 1], [3, 2], [1, 2], [3, 1], [2, 3], [2, 1], [3, 1], [3, 2], [1, 2], [1, 3], [2, 3], [1, 2], [3, 1], [3, 2], [1, 2], 

[1, 3], [2, 3], [2, 1], [3, 1], [2, 3], [1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2], [1, 2], [3, 1], [2, 3], [2, 1], [3, 1], [2, 3], [1, 2], [1, 3], [2, 3], [1, 2], [3, 1], [3, 2], [1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [2, 3], [1, 2], [1, 3], [2, 3]

반복되는 패턴이 보이긴 하는데 이걸 어떻게 적용해야 할지 어려움

적용될 조건도 확인

처음 원판을 옮길 때 원판의 개수가 홀수라면 목표 기둥의 반대 기둥(2번 기둥), 짝수라면 목표 기둥(3번 기둥) 으로 옮겨야 한다.
원판을 옮겼을 때 그 다음 행동은 원판이 옮겨진 기둥을 제외한 행동이다.

ex) 1에서 3으로 옮겼으면 1번 기둥이나 2번 기둥에서 옮겨야 한다.
원판을 옮길 때 이전에 위치한 기둥이 아닌 다른 기둥으로 옮겨야 한다.

ex) 1에서 3으로 옮긴 원판은 다음에 옮길 땐 2번 기둥으로 옮겨야 한다.

대가리 깨지기 전에 그냥 공유된 풀이를 확인함

def solution(n):
    def hanoi(start, target, temp, N):
        if N == 1:
            return [[start, target]]
        return hanoi(start, temp, target, N-1) + [[start, target]] + hanoi(temp, target, start, N-1)

    return hanoi(1, 3, 2, n)

hanoi(시작 위치, 도착 위치, 그 외 위치, 원판 개수)

n =1 일 때는 이동이 없으므로 바로 위치를 반환, 1 이상일 경우 재귀함수를 돈다

def solution(n):
    def hanoi(start, target, temp, N):
        if N == 1:
            return [[start, target]]
        return hanoi(start, temp, target, N-1) + [[start, target]] + hanoi(temp, target, start, N-1)

    return hanoi(1, 3, 2, n)

예시
# n=2
def hanoi(1, 3, 2, 2): 
	...
	return *hanoi(1, 2, 3, 1) + [[1, 3]] + **hanoi(2, 3, 1, 1)

* def hanoi(1, 2, 3, 1):
	if N == 1: 
		return [[1, 2]]

# *[[1, 2]] + [[1, 3]] + **hanoi(2, 3, 1, 1)

** def hanoi(2, 3, 1, 1):
	if N == 1: 
		return [[2, 3]]

# *[[1, 2]] + [[1, 3]] + **[[2, 3]]

결과
[[1,2], [1,3], [2,3]]