[알고리즘][파이썬] 백준_11729_하노이 탑 이동 순서

문제 지문의 그림을 보면 원판에 번호가 있다.

이 원판의 번호는 아무 의미 없으므로 무시해야 한다(원판은 크기가 중요).

규칙은 한 번에 한 개의 원판만 옮겨야 하고,

쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 하며,

이동 횟수는 최소가 되어야 한다.

[그림1]은 이해를 돕기 위해 원판 3개의 경우를 움직이는 그림으로 만들어 보았다.

 

[그림1] 하노이 탑 이동 순서

 

예제 입력이 3인 경우의 출력 결과는 다음과 같다.

7 # 원판을 옮긴 총 횟수
1 3 # (이하) 원판이 옮겨진 위치(예: 1번 장대에서 3번 장대로 이동)
1 2
3 2
1 3
2 1
2 3
1 3

 

예제 입력 3인 경우를 [그림2]로 나타내 보았다.

 

[그림2] 하노이 탑 이동 순서에 따른 출력 값

---

제출 코드

# 재귀함수 이용(결과: 맞았습니다!)

def hanoi(n, a, b, c):
    if n == 1:
        print(a, c)
    else:
        hanoi(n-1, a, c, b)
        print(a, c)
        hanoi(n-1, b, a, c)

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

 

매개변수 n은 원판의 수,

a, b, c는 장대이다.

원판은 장대 a에 위치해 있고,

최종적으로 c로 옮겨야 한다.

---

해결한 방법

재귀함수를 이용해 해결하였다.

재귀는 선언형 프로그래밍(declarative programming) 방법이라고 한다.

명령형 프로그램은 알고리즘을 명시하고 목표는 명시하지 않는 데 반해 선언형 프로그램은 목표를 명시하고 알고리즘을 명시하지 않는 것이다(위키백과).

제출한 코드에서는 다음과 같이 매개변수를 달리하며 재귀함수를 선언하였다.

hanoi(n, a, b, c)
hanoi(n, a, c, b) # 목표 : 오른쪽 장대 위치 변경
hanoi(n, b, a, c) # 목표 : 왼쪽 장대 위치 변경

위와 같이 장대 b를 기준으로 오른쪽 또는 왼쪽 매개변수(장대)의 위치를 바꾸면, 원판을 옮기는 것 처럼 기능을 구현할 수 있다.

 

코드의 실행 순서는 [그림3]과 같다.

[그림3] 코드 실행 순서(위에서 아래, 왼쪽에서 오른쪽 순)