[Python] 백준/BOJ 11729번: 하노이 탑 (Gold 5)

💻 Problem

문제 바로가기

 

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

 

💡 Approach

이전에 풀어봤던 문제지만 알고리즘을 오래 안 하면서 다 까먹어서 다시 풀어봤다.

하노이탑 규칙은 어렸을 때 많이 해봐서 이해하고 있었지만, 이를 어떻게 구현해야 할지 감이 안 왔다.

하노이탑이 헷갈린다면 플래시 게임에서 시뮬레이션 해볼 수 있다.

처음에는 원판의 개수가 홀수면 3번 장대로, 짝수면 2번 장대로 옮겨야 한다고 생각했었다.

 

이 문제가 재귀로 풀어야 한다는 건 알고 있었기에 함수의 역할과 매개변수, 종료 조건에 대해 고민해 봤다.

함수의 역할은 원판을 옮기는 것.

매개변수는 뭐가 필요할까. 옮기려는 원판의 index와 시작점, 도착점..?

종료 조건은 원판이 다 옮겨졌을 때인데.. 원판이 다 옮겨졌다는 걸 어떻게 판단할 수 있을까.

재귀는 큰 부분에서 작은 부분을 찾아야 하는데, 나는 자꾸 일을 순서대로 생각하여 재귀처럼 생각하는 것이 잘 안 됐다.

 

그래서 검색해 보면서 이해했는데 이 글이 이해가 잘되었다.

해당 글에서는 hanoi(n)에서 hanoi(n-1)이 발견되냐는 것에 대해 따지고 있는데 이 부분에서 제대로 이해할 수 있었다.

 

📍 초기 상태 - 원판 개수: 5

 

예를 들어, 5개의 원판이 있다고 치면 작은 4개의 원판이 어떻게 2번 장대로 옮겨졌는지는 중요하지 않다.

중요한 건 어찌 됐든 위의 4개 원판들은 어떻게든 2번 장대에  옮겨졌고, 가장 큰 원판을 도착점인 3번 장대에 옮겨야 한다는 것이다.

 

📍 원판 개수: 5, 시작점: 1, 도착점: 3, 경유지: 2

 

먼저 마지막 원판을 제외한 4개(n-1)의 원판들을 어떻게든 시작점(1)에서 경유지(2)로 옮기고 마지막 원판을 도착점(3)으로 옮긴다.

일단 4개의 원판들이 어떻게 경유지로 옮겨졌는지는 신경 쓰지 말자. 그건 재귀 들어가서 살펴볼 거다.

한 개의 원판을 도착점으로 옮겼으니 이제는 4개의 원판이 남았다. 다음 재귀로 들어가 보자.

 

📍 원판 개수: 4, 시작점: 2, 도착점: 3, 경유지: 1

 

마찬가지로 3개의 원판을 어떻게든 경유지(1)로 옮기고 4개 중 마지막 원판을 도착점(3)으로 옮긴다.

이후에는 3개의 원판을 가지고.. 2개의 원판을 가지고.. 위 내용을 재귀로 반복한다.

 

📍 원판 개수: 1

 

재귀를 반복하다 보면 원판 개수가 1개일 때가 올 텐데 그때가 재귀의 기저조건이다.

마지막 원판을 도착점(3)으로 옮겨주면 된다.

 

✏️ Solution 1

import sys
input = sys.stdin.readline

# 원판 개수, 시작점, 도착점, 경유지
def hanoi(k, start, end, via):
    # 기저 조건: k가 1일 때
    # k가 1이면 마지막 원반(가장 작은 원반)을 옮기고 끝낸다
    if k == 1:
        print(start, end)
        return

    # k-1개의 원판을 경유지로 옮긴다
    hanoi(k - 1, start, via, end)
    # k번째의 원판을 도착지로 옮긴다
    print(start, end)
    # k-1개의 원판을 도착지로 옮긴다
    hanoi(k - 1, via, end, start)

n = int(input()) # 원판의 개수
print(2 ** n - 1) # 옮긴 횟수
hanoi(n, 1, 3, 2)

 

옮긴 횟수는 공식이 있다.

공식을 사용하고 싶지 않다면 원판을 이동할 때 바로 출력하는 것 대신 튜플로 리스트에 담아서 옮긴 횟수를 세면 된다.

 

✏️ Solution 2

def hanoi(n, start, end):
    if n == 1:
        print(start, end)
        return
    
    hanoi(n-1, start, 6-start-end)
    print(start, end)
    hanoi(n-1, 6-start-end, end)

k = int(input())
print(2 ** k - 1)
hanoi(k, 1, 3)

 

과거에 제출했던 내역을 확인해 봤다. 이 코드엔 매개변수에 경유지가 없네?!?

 

하노이탑에는 1번 장대, 2번 장대, 3번 장대, 총 3개의 장대가 있다.

이를 다 더하면 6이 된다. (1+2+3)

즉, 우리는 start와 end의 번호를 알고 있으니 6에서 start와 end를 빼면 경유지의 번호를 구할 수 있는 것이다.