흑백돌 옮기기 문제

문제

To solve the swapping puzzle, use only two types of moves. Move one stone into the empty hole or jump one stone over one stone of the opposite color (into the empty hole)

You may not back up, and you may not jump over two stones.

/*Visual Studio 2015*/
/*C++*/

#include<iostream>  
#pragma warning(disable:4996) //scanf warning 해제
using namespace std;
#define MAX 180
int n = 3, idx;
int res[MAX];//움직인 돌의 위치를 저장할 배열
char state[MAX];//현재 돌의 배열상태를 나타낼 배열
void init()//초기화
{
	idx = 1;//몇번 움직였는지 카운트 할 인덱스
	for (int i = 1; i <= n; i++)//1~n번째 돌은 흰색
		state[i] = 'W';
	state[n + 1] = ' ';//n+1번째는 빈칸
	for (int i = n + 2; i <= 2 * n + 1; i++)//n+2번째 부터 2n+1까지 검은돌
		state[i] = 'B';
}
void swap(int &x, int &y)//돌의 위치를 바꾸는 함수
{
	int t;
	t = x;
	x = y;
	y = t;
}

void sum_show()//움직인 돌의 위치를 보여주는 함수
{//총 20개가 넘으면 개행하도록 함
	int sum = 0;
	for (int i = 1; i <= n*(n + 2); i++)
	{
		if (sum % 20 == 0)
			printf("%d", res[i]);
		else printf(" %d", res[i]);
		sum++;
		if (sum % 20 == 0)
			printf("\n");
	}
	if (sum % 20)
		printf("\n");
}

void puzzle(int hole, int cnt)//hole은 빈칸의 위치, cnt는 움직인 횟수
{
	if (cnt == idx)
		idx++;
	if (hole - 2>0 && state[hole - 2] == 'W' && state[hole - 1] == 'B')
	{//빈칸의 왼쪽에 2개 이상의 돌이 있고, 빈칸에서 왼쪽으로 2칸은 W, 1칸은 B일때
		swap(state[hole - 2], state[hole]);//빈칸 왼쪽에서 두번째 자리에 위치한 돌을 빈칸으로 점프
		res[cnt] = hole - 2;//움직인 돌은 빈칸에서 왼쪽으로 두번째 있는 돌이므로, res에 해당 위치를 저장
		if (cnt == n*(n + 2) && hole - 2 == n + 1)//답이라면(cnt가 2^n+2n이고, 빈칸의 위치가 가운데일경우
		{
			sum_show();//결과를 보여주고
			return;//리턴
		}
		else if (cnt<n*(n + 2))//답보다 작다면
			puzzle(hole - 2, cnt + 1);//현재 빈칸의 위치는 원래 빈칸에서 왼쪽으로 두칸 이동하였다.
									//돌이 움직인 횟수가 1 증가인 상태로 재귀호출
		swap(state[hole - 2], state[hole]);
	}
	if (hole - 1>0 && state[hole - 1] == 'W')//빈칸의 왼쪽에 1개 이상의 돌이 있고, 바로 왼쪽의 돌은 W일때
	{
		swap(state[hole - 1], state[hole]);//왼쪽에 있는 돌을 빈칸으로 옮긴다.
		res[cnt] = hole - 1;//움직인 돌은 빈칸 왼쪽에 있던 돌이였으므로, res에 추가한다.
		if (cnt == n*(n + 2) && hole - 1 == n + 1)//답이라면 답을 보여주고 리턴
		{
			sum_show();
			return;
		}
		else if (cnt<n*(n + 2))//답보다 작다면
			puzzle(hole - 1, cnt + 1);//빈칸의 위치는 하나 밀렸고 이동횟수는 1 증가
		swap(state[hole - 1], state[hole]);
	}
	if (hole + 1 <= 2 * n + 1 && state[hole + 1] == 'B')
	{
		swap(state[hole + 1], state[hole]);
		res[cnt] = hole + 1;
		if (cnt == n*(n + 2) && hole + 1 == n + 1)
		{
			sum_show();
			return;
		}
		if (cnt<n*(n + 2))
			puzzle(hole + 1, cnt + 1);
		swap(state[hole + 1], state[hole]);
	}
	if (hole + 2 <= 2 * n + 1 && state[hole + 2] == 'B' && state[hole + 1] == 'W')
	{
		swap(state[hole + 2], state[hole]);
		res[cnt] = hole + 2;
		if (cnt == n*(n + 2) && hole + 2 == n + 1)
		{
			sum_show();
			return;
		}
		if (cnt<n*(n + 2))
			puzzle(hole + 2, cnt + 1);
		swap(state[hole + 2], state[hole]);
	}
}
void main()
{
	while (n != 0)//0을 입력받을때까지 루프를 돌림
	{
		printf("input n = ");
		scanf("%d", &n);//n을 입력받음
		init();
		puzzle(n + 1, 1);//인덱스를 1부터 시작하기 위해 n+1을 대입
		printf("result : %d\n\n", idx - 1);//1부터 시작하였기에 -1을 하여 올바른 결과가 나오도록 함
	}
}