파이썬(Python) 알고리즘 문제풀이 하노이의 탑 [프로그래머스 / 문자열]

출처) 프로그래머스 Facebook

문제 설명

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

 

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

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

 

 

제한사항

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

 

 

입출력 예시

n	result
2	[ [1,2], [1,3], [2,3] ]

 

 

풀이 코드

재귀 함수 알고리즘을 이해하는데 가장 대표적인 문제로 알고 있었는데, 대표적인 문제 치곤 생각하기 어려웠다. 

https://www.youtube.com/watch?v=aPYE0anPZqI&t=310s 얄코님 유튜브를 참고해 가까스로 이해 후 풀이했고 하나 씩 살펴보자.

 

n = 2 라고 가정한 입출력 예시로는 이해하기 부족하니 n = 3 인 경우를 그려본다면, 하노이의 탑에서 가장 우선시 되는 전제는 제일 큰 원반이 목적지의 맨 아래에 놓여져야하고 이걸 위해서 제일 큰 원반을 제외한 나머지 원반들이 출발지, 목적지 기둥이 아닌 경유지 기둥에 놓여져 있어야 한다는 것이다. 경유지니 목적지니 헷갈릴 수도 있는데, 경유지와 목적지는 현재 상황에서의 논리적인 경유, 목적지를 의미하는 것이고 재귀가 호출 될 때 마다 실질적으로 경유, 목적지가 계속해서 바뀌는 것을 유의하자.

 

이미지를 코드로 구현

def hanoi(n, start, to, mid, answer):
	if n == 1:
    	# 가장 작은 원반만이 남았으니 to 기둥으로 옮김
    	return answer.append([start, to])
        
	# (start, mid, to) - 현재 목표 기둥은 2번 mid 기둥, 경유 기둥은 3번 to 기둥이라는 뜻
    # 경유 기둥이 to 기둥이라고 해서 to 기둥이 목표 기둥이 아닌 것은 아님 (헷갈리지 말기) 단지 경유하는 것 뿐
    hanoi(n - 1, start, mid, to, answer)
    
    # n - 1 개의 원반을 목표 기둥으로 옮겼으면, 나머지 남은 현재 가장 큰 원반을 to 기둥으로 옮김
    answer.append([start, to])
    
    # (mid, to, start) - 현재 목표 기둥은 3번 to 기둥, 경유 기둥은 1번 start 기둥이라는 뜻
    hanoi(n - 1, mid, to, start, answer)

def solution(n):
	answer = []
    
    # 재귀 호출 시작
    # 기둥의 기준을 명시 (start - 1번 기둥, to - 3번 기둥, mid - 2번 기둥)
    hanoi(n, 1, 3, 2, answer)
    
    return answer