[알고리즘 문제 풀이][재귀] 백준 11729번 - 하노이 탑 이동 순서 / 1914 번 - 하노이 탑

백준 11729번 하노이 탑 이동 순서 / 1914번 하노이 탑 문제입니다.

(재귀)

 

- 문제 설명: https://www.acmicpc.net/problem/11729

- 문제 풀이:

 

백준 단계별로 풀어보기의 '재귀' 연습 문제입니다. (https://www.acmicpc.net/step/19)

하노이 탑은 시작점에 있는 원판들을 도착점으로 옮기는 것인데, 직접 이동시켜보면 최소 이동 횟수가 2^n - 1 개가 나오는 것을 알 수 있습니다.

 

왜 그렇게 나오는지 재귀적으로 생각해보면 다음과 같습니다.

원판이 3개 있는 경우를 살펴보겠습니다.

그러면 맨 마지막 3번째 칸이 맨 끝 도착지점에 가기 위해서는 반드시 위의 2개의 원판이 가운데 지점에 놓여야합니다.

그래야 3번째 원판을 도착 지점에 먼저 깔고 작은 2개의 원판을 그 위로 이동시킬 수 있습니다.

그러므로 맨 마지막 원판을 이동시키기 위해 그 위에 놓인 원판들을 임시 지점을 이동시키고, 맨 마지막 원판을 이동한 후에, 다시 임시 지점에 둔 원판들을 자기 위로 데려오면 됩니다.

이 부분을 코드로 보면 다음과 같습니다.

hanoi(start, temp, end, disc-1) # 맨 마지막 원판 위에 거들을 다 임시 지점으로 옮기기
print(start, end) # 맨 마지막 원판을 도착지점으로 옮기기
hanoi(temp, end, start, disc-1) # 임시 지점의 원판들을 맨 마지막 원판 위로 옮기기

아직 이해가 잘 되지 않는다면, 위의 예시에서 작은 원판을 옮기는 과정을 한 번 더 보겠습니다. 이번에는 맨 마지막 원판은 신경 쓰지 않고, 중간 원판을 마지막 원판이라고 생각하겠습니다.

아까 작은 원판 두 개를 임시 지점에 도착 시키는 것이 목표였으므로, 중간 원판은 최종 도착점이 가운데 임시 지점이 됩니다. 그러기 위해서는 위의 원판들을 모두 (지금은 제일 작은 원판 1개가 위에 얹혀진 원판의 전부이지만...) 도착점을 임시점으로 생각하고 이동해야합니다.

그러면 임시 지점에 올려져있던 것들을 최종적으로 도착점 위에 깔린 원판 위에 올려주면 됩니다.

여기까지하면 아까 코드로도 본 첫번째 재귀함수 하나가 실행 완료된 모습이 됩니다. 이 문제를 푸는데 중요한 것은 재귀를 돌 때마다 시작점, 임시 지점, 도착점이 고정되어있지 않다는 것입니다. 그때마다 시작하는 위치와 도착하고자 하는 위치가 달라집니다. 그걸 고려해서 재귀를 타고 들어가게 코드를 짜면 됩니다.

 

- 코드: 

def hanoi(start, end, temp, disc):
    if disc == 1:
        print(start, end)
    else:
        hanoi(start, temp, end, disc-1)
        print(start, end)
        hanoi(temp, end, start, disc-1)

N = int(input())
print(2**N - 1)
if N <= 20:
    hanoi(1, 3, 2, N)

 

- 실수 포인트 & 반례:

1. 본 문제는 별 다른 반례가 없습니다. 2, 3, 4 인풋의 경우 답은 다음과 같습니다.

입력)
2

정답)
3
1 2
1 3
2 3

입력)
3

정답)
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

입력)
4

정답)
15
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