하노이의 탑(프로그래머스-level3)

안녕하세요 강민성입니다.

프로그래머스에서 문제를 풀다보면 다음과 같은 문구를 보실 수 있을 겁니다. 

# 알고리즘 연습 문제가 개편 되었습니다. 이로 인해 함수 구성이 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.

말 그대로 18년 5월 정도 부터 문제들이 약간씩 바뀌고 문제가 같더라도 테스트 케이스가 더 복잡해지고 정교해져서

옛날 풀이도 정답이 아닐 수 있습니다.

다른 블로그에 포스팅 된 글이나 프로그래머스 내에서 다른 사람의 풀이를 보실 때 참고하시길 바랍니다.

저는 개편된 후의 풀이임을 알립니다.

오늘 소개해드릴 문제는 제목에서 알 수 있듯이 하노이의 탑입니다.

아마 어디서 한 번 쯤은 들어보셨을 거라고 생각을 해요.

저도 고등학교 때 교과서에 나와서 접했던 기억이 있는데

이렇게 코드로 구현해보니까 새로웠습니다. 

문제를 설명 드리자면

[ question ]

하노이 탑(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] ]

입출력 예 #1

다음과 같이 옮길 수 있습니다.

 

사실 하노이탑이 재귀적인 과정을 통해 이루어진다는 점을 이미 알고 있어서 

방향을 잘 잡을 수 있었습니다.

하지만 코드로 구현하는데 있어서는 이를 알고 있어도 애를 쫌 먹었는데

하노이탑을 처음 봤으면 문제를 푸실 때 어려움을 느끼실 거라고 생각이 듭니다.

풀이 코드부터 보여드리고 하노이탑이 어떻게 재귀적으로 이루어지는 설명을 해드리도록 하겠습니다.

#[ my answer ]
 
hanoi = [] # hanoi 라는 빈 배열 생성
 
def han(n, first,semi, final): # 원판의 개수, 처음시작하는 기둥, 중간기둥
                                # 마지막 기둥을 매개변수로 받는 함수
    if n == 1: # 원판이 하나 일 때는
 
        hanoi.append([first,final]) # 배열에 첫번째에서 세번째로 옮긴다는 라는 뜻으로
                                     # [first,final] 을 추가해준다.
    else: # 원판이 하나가 아닐 때는 아래와 같은 과정을 수행한다.
 
        han(n-1,first, final, semi) # n-1개의 원판을 첫번째에서 중간으로 옮기고
 
        han(1, first, semi, final) # 1개의 원판을 첫번째에서 마지막으로
 
        han(n-1, semi, first, final) # 다시 n-1개의 원판을 중간에서 마지막으로 옮긴다.
 
    return hanoi # hanoi 배열을 결과 값으로 return 하고
    
def solution(n): # 문제를 해결하는 함수
 
    answer = han(n, 1,2,3) # 첫번째 기둥에서 두 번째 기둥을 통해 세번째 기둥으로 n개의 원판을 옮긴다.
 
    return answer
 

다음과 같은 코드로 하노이 탑을 옮기는 방법을 나타낼 수 있습니다.

주석을 통해 각 코드에 대한 설명을 하였고 

13 ~ 17번째 코드가 중요하므로 그 부분만 다시 봐보도록 하겠습니다.

n개의 원판을 첫번째 기둥에서 마지막 기둥에서 옮기기 위해서

n-1개의 원판을 첫번째에서 두번째 기둥으로 

1개의 원판을 첫번째에서 세번째 기둥으로

다시 아까 옮겼던 n-1개의 원판을 두번째 기둥에서 세번째 기둥으로 옮기게 됩니다.

그림으로 보면 다음과 같습니다.

다음과 같이 재귀적으로 문제를 해결하였는데

 사실 알고리즘에서 재귀함수를 썼을 때 항상 시간복잡도의 문제로 실패했었습니다.

그 만큼 재귀함수를 사용할 시 복잡도가 기하급수적으로 증가하게 되는데

다행히도 이 문제에서는 n의 값을 15이하의 자연수로 제한했기에 문제가 없었습니다.

재귀적으로 해결하는 가장 대표적인 하노이의 탑을 알아보았습니다.

이제부터는 다른 재귀적인 문제가 나와도 잘 해결하실거라 믿습니다 ㅎㅎ