[프로그래머스💯] 코딩테스트 연습 > 연습문제 > 하노이의 탑 / Python 문제풀이

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

def solution(n):
    res = []
    blocks = [1, 2, 3]

    def getLastBlock(block1, block2):
        for b in blocks:
            if b != block1 and b != block2:
                return b

    def move(blockCount, start, dest):
        if blockCount == 1:
            return res.append([start, dest])
        lastBlock = getLastBlock(start, dest)
        move(blockCount-1, start, lastBlock)  # 일단 나머지 블록에 옮긴다.
        res.append([start, dest])  # 맨밑 블록 하나를 목적지에올린다.
        move(blockCount-1, lastBlock, dest)  # 나머지 블록에 있던거 목적지로
        return True
    move(n, 1, 3)
    print(res)
    return res

'''
1->3 으로 5개 옮긴다고 쳤을 때,
1->2 로 4개 옮기고 1->3 1개  그다음 2->3 으로 4개
1->2 로 4개 옮긴다고 쳤을 때,
4개 옮기고 1->3 1개  그다음 2->3 으로 4개
3개 옮긴다고 쳤을 때,
1->2 로 4개 옮기고 1->3 1개  그다음 2->3 으로 4개
2개 옮긴다고 쳤을 때,
1->2 로 4개 옮기고 1->3 1개  그다음 2->3 으로 4개
1개 옮긴다고 쳤을 때,
1->2 로 4개 옮기고 1->3 1개  그다음 2->3 으로 4개
'''

풀이)

하노이의 탑의 기본 원리 

 

2개를 기둥 3에 옮기는 것 : 블럭 1개를 기둥 2에 옮기고 남은 1개를 기둥 3에 옮긴다. 

3개를 3에 옮기는 것 :

1. 블럭 2개를 기둥 2에 옮긴다.

2. 남은 1개를 기둥 3에 옮긴다.

3. 방금 기둥 2에 옮겨놨던 것을 다시 기둥 3에 옮긴다. 

 

 

블럭의 개수가 몇개가 되던 이런식으로 옮겨지게 된다.

 

 

1단계 : 기둥 1에 꽂혀 있는 n-1개의 원판을 기둥2 로 옮긴다.

2단계 : 기둥 1에 남은 1개의 가장 큰 원판을 기둥3ㅇ으로  옮긴다.

3단계 : 기둥 2의 n-1개의 원판을 기둥3으로 옮긴다.

 

코드 구현

 

출발지, 목적지에 갈때를 표현한 move함수를 만든다.

블럭이 이동할때마다 리스트에 이동한 trace를 넣어준다.

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges