백준 11729 - 하노이의 탑 이동순서

본 문제는 입력으로 주어지는 n 개의 원판을 이동시키는 회수와 방법을 표시해야 하는 문제이며 이동회수가 회수가 최소가 되는 방법은 단 한가지 방법 뿐입니다.

 재귀호출을 통해 풀이할수있는 가장 기본적인 형태의 문제입니다. 재귀호출은 기저조건 즉 재귀호출을 탈출할수 있는 조건 을 가장 먼저 정의해야 합니다. 그렇지 않으면 문제 풀이 중 무한 루프에 빠지다가 스텍오버플로우 로 프로그램이 죽을 것 입니다.

 본 문제의 기저조건은  옮길  스톤이 1개 일 때 입니다. 출발지에서 목적으로 1회 이동 하도록 구현하면 됩니다.

스톤이 한개 이상일 때는 제일 바닥의 돌과 그위의 돌들로 분류해서 생각할 수 있고 아래와 같이 세단계를 거쳐서 이동시킵니다.

  step1) 1~N-1 의 스톤을 중간 막대기로 이동시킵니다.

  step2) N 번째 스톤을  목적지 막대기로 이동시킵니다.

  step3) 1~N-1 의 스톤을 목적지 막대기로 이동시킵니다. 

1~N-1 스톤을 이동시키기 위해 재귀호출을 수행하면 됩니다.

전체 수행회수는 2^N-1 입니다.

코드로 구현하면 아래와 같습니다.

 

#include <math.h>
#include <iostream>

using namespace std;

void moveStone(int s, int e, int src, int dest);

int main()
{
	int nrT;
	scanf("%d", &nrT);
	printf("%d\n", (int)pow(2, nrT) - 1);
	moveStone(1, nrT, 1, 3);
}

void moveStone(int s, int e, int src, int dest)
{
	int mid = 6 - src - dest;
	int size = e - s + 1;
	if (size == 1)
	{
		printf("%d %d\n", src, dest);
		return;
	}
	moveStone(s, e-1 , src, mid);
	printf("%d %d\n", src, dest);
	moveStone(s, e-1, mid, dest);
}