[프로그래머스] 하노이 탑 (Python)

Source

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

Code

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

def hanoi(n, start, end, mid, answer):
    if n == 1:
        # 원반이 하나일 경우 그냥 옮겨 주면 됨
        return answer.append([start, end])

    hanoi(n - 1, start, mid, end, answer)
    # 1. n - 1 개의 원반을 end 기둥을 사용해서 start에서 mid로 옮긴다.
    answer.append([start, end])
    # 2. start 기둥에 남아 있는 가장 큰 원반을 end로 옮긴다.
    hanoi(n - 1, mid, end, start, answer)
    # 3. n - 1 개의 원반을 start 기둥을 사용해서 mid에서 end로 옮긴다.

 

How to solve?

선언적 프로그래밍 방식으로 재귀 코드를 작성 해준다.

1. n - 1 개의 원반을 end 기둥을 사용해서 start에서 mid로 옮긴다.

2. start 기둥에 남아 있는 가장 큰 원반을 end로 옮긴다.

3. n - 1 개의 원반을 start 기둥을 사용해서 mid에서 end로 옮긴다.

 

1과 3의 과정에서 다시 재귀적으로 같은 과정이 반복된다.

n = 1인 경우 start에서 바로 end로 원반을 옮겨준다.