[알고리즘] 하노이의 탑

※ 문제 출처

• 프로그래머스 lv3. 하노이의 탑

1. 문제 개요

이 문제는 오래된 고전 문제 중 하나로 이해하기 어렵지 않다.

기둥은 3개가 있으며, 1번 원반에 N개의 원판이 있다. 이 N개의 원판을 모두 3번 기둥으로 옮기는 최소 횟수를 구하도록 한다.

• 제약 조건
  -> 원판을 쌓을 때는 항상 큰 원판이 작은 원판보다 아래에 위치해야한다.

-> 즉, 1번 기둥에 쌓인 원판의 순서 그대로 3번 기둥으로 옮겨야 한다.

2. 풀이

1) 알고리즘 개요

① 1번 기둥 최하단의 원판을 3번 기둥 최하단으로 옮겨야 한다.
② 이를 위해 1번 기둥의 최하단 제외(N-1)개의 기둥은 2번 기둥으로 옮겨야 한다.
③ N-1개의 기둥을 2번 기둥으로 옮기는 과정을 위해 N-2개의 원판이 다른 기둥으로 옮겨져야 한다.
...
개요를 정리하다보면 재귀 함수 이용이 떠오른다.

2) 알고리즘 풀이

hanoi 함수를 설계하도록 한다.

• input value
  ⓐ int n : 움직일 원판 갯수
  ⓑ int from : 출발 기둥
  ⓒ int by : 경유지
  ⓓ int to : 도착 기둥

3) c++ 코드

// 1번 기둥->(2번기둥)->3번기둥
void hanoi(int n, int from,int by, int to)
{
	if(n==1)
    	;
    else
    {
    	// n-1개 : 1번기둥->3번기둥을 거쳐->2번기둥
    	hanoi(n-1,from,to,by);
        // n-1개 : 2번기둥->1번기둥을 거쳐->3번기둥
        hanoi(n-1,by,from,to);
    }
}