백준 BaekJoon Online Judge // 11729

 백준 알고리즘 BaekJoon Online Judge 11729번 "하노이 탑 이동 순서" 문제입니다.

def hanoi(N, fr, through, to):
  if N == 1:
    print(fr, to)
  else:
    hanoi(N-1, fr, to, through)
    print(fr, to)
    hanoi(N-1, through, fr, to)

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

유명한 하노이의 탑 문제를 재귀 함수로 푸는 문제다.

 

하노이의 탑

1번에서 크기가 큰 원판부터 가장 작은 원판까지 쌓여있는 탑을 3번으로 옮기는 문제다. 

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

이 문제를 효율적으로 풀기 위해서는 하노이의 탑의 횟수를 구하는 공식을 알아야 한다.

이는 아래의 링크에 첨부하겠다. 아래의 링크에 증명도 자세하게 되어있다.

johngrib.github.io/wiki/tower-of-hanoi/

하노이의 탑 (The Tower of Hanoi)

원리는 아래와 같다.

1번에서 2번을 거쳐 3번으로 옮겨야 하는데 이는 과정을 쪼개면

-> 1번에서 2번으로 맨 밑판을 남기고 규칙에 맞춰서 옮긴다.

-> 1번의 맨 밑판을 3번으로 옮긴다.

-> 2번의 나머지 판들을 규칙에 맞춰서 3번으로 옮긴다.

이렇게 쪼갤 수 있다. 즉 1번 과정은 hanoi(N-1, from, to, through)

2번 과정은 print(from, to), 3번 과정은 hanoi(N-1, through, from, to)를 나타낸다.