[백준] 11729 하노이 탑 이동 순서(Python)

해당 게시글에서는 [백준] 11729 하노이 탑 이동 순서 문제를 해설하고 Python을 이용하여 풀고자 한다.

💡 문제 풀이

11729번 문제는 재귀(recursion)로 유명한 하노이 탑 문제에 해당한다.

해당 문제에서는 입력된 초기 원판의 개수에 대해 하노이 탑 규칙에 따라 모든 원판을 이동시킬 때 옮긴 횟수(K)와 이동 경로를 출력해야 한다.

하노이 탑을 재귀적으로 구현하기 위해 원판 개수에 따라 반복되는 과정이 있는지 고민하는 시간을 가졌으며, 그 결과는 다음과 같다.

• N개의 원판을 모두 옮기기 위해, 먼저 N-1개의 원판(가장 큰 원판을 제외한 나머지)을 다른 장대로 옮긴다.
• 가장 큰 원판을 세 번째 장대로 옮긴다.
• 이전에 옮긴 N-1개의 원판을 세 번째 장대로 옮긴다.

 

위의 내용을 통해 재귀적으로 코드를 작성하면 다음과 같다. 자세한 코드는 아래를 참고하길 바란다.

hanoi(N-1, start, end, via) # N-1개의 원판 이동
hanoi(1, start, via, end) # 가장 큰 원판 이동
hanoi(N-1, via, start, end) # N-1개의 원판을 가장 큰 원판 위로 이동

 

📂 코드

• start: 시작하는 장대
• via: 경유하는 장대
• end: 최종으로 모든 원판이 도착하는 장대

global move
move = []

def hanoi(N, start, via, end):

    // :param N: 원판의 수
    // :param start: 시작 기둥
    // :param via: 중간 기둥
    // :param end: 끝 기둥
    // :return: 이동 횟수

    if N <= 1: # 원판이 1개 있는 경우
        move.append((start, end))
        return 1

    cnt = 0
    cnt += hanoi(N-1, start, end, via) # N-1개의 원판을 보조 기둥에 모두 이동
    cnt += hanoi(1, start, via, end) # 가장 큰 원판을 끝 기둥에 이동
    cnt += hanoi(N-1, via, start, end) # N-1개의 원판을 끝 기둥에 이동
    return cnt

print(hanoi(int(input()), 1, 2, 3))
for f, t in move:
    print(f, t)