99클럽 코테 스터디 7/99일차 TIL #하노이의 탑(미들러)

문제:전화번호 목록호 목록

출처: 프로그래머스

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

1. 문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

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

2. 문제 해석

재귀....재귀다.

우선은 문제를 처음 봤을 때 재귀 쓰는건 알겠는데 result 값을 이해하는데 조금 시간이 걸렸다.

문제에 오타도 있었고(매우 핑계)

3개의 기둥
1번 기둥에 n개의 원판 존재
n개의 원판을 3번 기둥으로 옮기는 최소 횟수

result 값을 이해하기 위해 case들을 하나씩 작성해 보았다.

2개의 원판이 1번 기둥에 있으면 맨 아래 원판을 3번에 먼저, 그 다음 원판을 그 위에 옮겨야 한다.

그래서 [ [1,2], [1,3], [2,3] ] 값을 이해해 보면

[1,2]:1번 기둥에 있는 원판을 2번 기둥으로(맨 위 원판)

[1,3]: 1번 기둥에 있는 2번째 원판을 3번 기둥으로(맨 아래 원판)

[2,3]: 2번 기둥으로 임시로 옮겨 놓은 윗 원판을 3번 기둥으로 옮긴다.

를 말하는 것이다.

이를 하나씩 작성해 가면서 재귀를 어떻게 쓸 지 고민ㅇ..을 하다가 등비수열로 생각이 산으로 가버렸다.

result 값을 이해하기
1 -> 2^0 
[1,3] 
2 -> 2^0+2^1
[1,2],
[1,3],[2,3]
3 -> 2^0+2^1+2^2
[1,3],
[1,2],[3,2],
[1,3],[2,1],[2,3],[1,3]
4 -> 2^0+2^1+2^2+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]
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]

n -> 2^0+2^1+ ... + 2^(n-1)

n번째 정답 배열의 개수는 저렇게 등비수열의 합으로 나오긴 하겠는데, 각 횟수를 어떻게 만들지 하다가

홀수때와 짝수때가 나뉘지는 것 같다. 정도로 하고 생각한 제한시간이 넘어 중단했다.

 

3. 문제 풀이

풀이 (1) 100/100

위에서 문제를 이해하면서 n번째 까지는 어떻게 생각을 했는데 재귀의 기본 형식이 되는 n-1, n, n+1에 대한 생각까지 다다르지 못했었다.(매우 아쉽)

우선 재귀함수는 base case가 필수다.

여기서는 n=1인 경우가 base case가 될 것이다.

n개의 원판이 있는 경우를 생각을 해보면,

n-1개의 원판이 2번째 기둥으로 옮긴다. why?: 맨 마지막 원판인 n번째의 원판이 3번째 기둥의 맨 마지막으로 가야하므로

그 다음 맨 마지막 원판인 n번째 원판을 3번째 기둥으로 마지막으로 옮기면 끝난다!

간단하지만 재귀를 쓰는 기본적인 개념을 까먹으니 코드 한 줄도 쓰지 못했다.

 

def hanoi(n, start, via, end, answer):
    
    if n == 1:
        answer.append([start, end])
        
    else:
        hanoi(n-1, start, end, via, answer)
        answer.append([start, end])
        hanoi(n-1, via, start, end, answer)

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

위 코드의 기본적인 컨셉은 재귀 함수를 hanoi로 만들고 봉의 번호가 1,2,3 어떤 것인지 모르기 때문에 start, via, end 라는 표현을 넣었다.

그리고 재귀 방식은 n 번째 원판을 3번째, 즉 end에 꽂으려면 n-1번째의 원판이 1번째에서 2번째로 옮겨저야 한다.

이는 한 번에 되는게 아니라 3번째의 기둥을 보조 기둥의 역할로 사용한다. -> 이것 때문에 재귀가 들어감

그 다음 맨 마지막의 n번째의 원판을 1번 기둥에서 3번 기둥으로 옮긴다(start -> end)

: hanoi(n-1, start, end, via, answer)

그리고 이 경우가 기록이 되어야 하므로 anwer에 append 한다.

: answer.append([start, end]) 로 append 함.

그러면 남은 n-1개의 원판은 n번째 원판을 움직이기 위해 2번 기둥에 전부 가있다.(via)

그래서 이 남은 n-1개의 원판을 via에서 end로 옮기고, 보조 역할로 start 기둥을 사용한다.

: hanoi(n, via, start, end, answer)

마지막으로 재귀의 base case, 즉 무한 루프를 탈출하기 위해서 n=1, 맨 마지막 원판이 남은 경우를 설정한다.

: answer.append([start, end])

 

 

 

4. 주요 코드 및 정리

하노이의 탑은 워낙에 유명한 재귀 함수 대표 문제인데 안쓰다 보니 까먹고 있었다.

재귀를 코드로 바로 치기 전에 다음 과정으로 진행할 것

1) 1,2,3 정도의 case에 대해 손으로 작성.

2) n의 case 확인

3) n-1의 case 확인

4) base case 확인