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

[문제링크] https://school.programmers.co.kr/learn/courses/30/lessons/12946

문제 설명

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

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

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

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

제한사항

• n은 15이하의 자연수 입니다.

---

입출력 예

입출력 예 설명

입출력 예 #1
다음과 같이 옮길 수 있습니다.

 

알고리즘

아이디어 출처: https://daebaq27.tistory.com/107

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

아이디어의 핵심을 다음과 같다.

1. 먼저, 재귀함수의 탈출 조건은 n=1일 때이다. 

명백하다. 원판이 하나만 있고, 시작지점과 끝지점을 알고 있으면, 원판을 시작지점에서 끝지점으로 옮기기만 하면 된다.

return start --> end

가 되는 방식으로 return만 하면 된다.

 

2. n개의 원판을 옮기기 위해서

1. n-1개의 원판을 1 -> 2로 이동한다.(재귀)
2. 1개의 원판을 1 -> 3으로 이동한다.
3. n-1개의 원판을 2 -> 3으로 이동한다.(재귀)

이것만 이해하면 간단하게 풀 수 있다. (여기까지만 읽어보고 한 번 시도해볼 것을 추천)

간단하게 점화식으로 작성해 보았다.

'''
1에서 3로 n개를 이동하는 함수를 f라고 한다면
'''
f(n, 1, 3) = f(n-1, 1, 2) + f(1, 1, 3) + f(n-1, 2, 3)

여기서 난관을 두 개 부딪혔음.

 

1. 1에서 3으로 가는 함수만 작성했는데, 1에서 2로 가는 경우를 코드로 어떻게 해야하나.

• 1) (1, 2)부터 (2, 3), (3, 2) 등 모든 경우의 수를 다 적는다. --> 너무 무식한 짓이었다. 그래서,
• 2) 규칙을 파악했다. 내가 고려해야하는 경우의 수는 다음과 같다.
  • 1, 2 -->3
  • 1, 3 --> 2
  • 2, 3 --> 1
  • 2, 1 -->3
  • 3, 1 --> 2
  • 3, 2 --> 1

여기서 모든 경우의 공통점은 각 경우에서 1, 2, 3이 모두 포함되어야 한다는 점. 따라서 세 수의 합이 6이라는 점이다. 그래서 나는 waypoint라는 변수를 추가해서 다음과 같이 썼다.

waypoint = 6 - (start + end)

2. 리스트를 어떻게 하면 출력 요구사항에 맞출 수 있을까?

- 이 부분은 n = 1일 때, 그리고 n = 2일 때를 머릿속으로 생각하면서 출력 형식을 맞춰보니, 처음 return할 때 이중으로 리스트를 쓰면 되더라.

전체코드

'''
f(1, 1, 3) --> [1, 3]
f(2, 1, 3) --> [[1, 2], [1, 3], [2, 3]]

n개의 원판을 1에서 3으로 옮기는 것은
f(n, 1, 3) = f(n-1, 1, 2) + f(1, 1, 3) + f(n-1, 2, 3)
n-1개를 1에서 2로 옮기고 --> 1개를 1에서 3으로 옮기고 --> n-1개를 2에서 3으로 옮기는 것과 같다.

'''
def hanoi(n, start, end):
    if n == 1:
        return [[start, end]]
    waypoint = 6 - (start + end)
    
    return hanoi(n-1, start, waypoint) + hanoi(1, start, end) + hanoi(n-1, waypoint, end)

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

 

소감

하노이의 탑은 대표적인 재귀 함수 문제라고 한다.

첫째날, 기둥 리스트를 만들어 풀어보려고 했다. 어떻게 풀지 감이 1도 안왔다. 고민고민하다가 패스

둘째날, 역시 답이 1도 생각이 안나서 그냥 블로그를 찾았다. 일단 설명만 읽고 풀어보자 싶어서 설명만 보고 풀었는데, 어찌어찌 풀었다. 후~ 아직 많이 부족하다. 화이팅