식인종과선교사문제/조현태 ¶

소스 ¶

~cpp
#include <vector>
#include <map>

using namespace std;

typedef struct party {
	party()
	{
		white = 0;
		black = 0;
	}
	party(int inputWhite, int inputBlack)
	{
		white = inputWhite;
		black = inputBlack;
	}
	int white;
	int black;
} party;

const int NUMBER_MOVE_TYPE = 5;
const int CAN_MOVE_WHITE[NUMBER_MOVE_TYPE] = {0, 0, 1, 1, 2};
const int CAN_MOVE_BLACK[NUMBER_MOVE_TYPE] = {1, 2, 0, 1, 0};

bool isOK(party& left, party& right)
{
	if (0 > left.black || 0 > left.white || 0 > right.white || 0 > right.black)
		return false;
	if (left.black > left.white && 0 != left.white)
		return false;
	if (right.black > right.white && 0 != right.white)
		return false;
	return true;
}

bool isEnd(party& left)
{
	if (0 == left.black && 0 == left.white)
		return true;
	return false;
}

int Parse(party& left, party& right, int where)
{
	return where * 10000 + left.white * 1000 + left.black * 100 + right.white * 10 + right.black;
}

bool MoveNext(vector<party>& moveData, map<int, bool>& isChecked, int where, party left, party right)
{
	if (isChecked[Parse(left, right, where)])
		return false;
	isChecked[Parse(left, right, where)] = true;
	if (false == isOK(left, right))
		return false;
	if (isEnd(left))
		return true;
	party testLeft, testRight;
	for (register int i = 0; i < NUMBER_MOVE_TYPE; ++i)
	{
		testLeft.white = left.white + CAN_MOVE_WHITE[i] * where;
		testLeft.black = left.black + CAN_MOVE_BLACK[i] * where;
		testRight.white = right.white + CAN_MOVE_WHITE[i] * (where * (-1));
		testRight.black = right.black + CAN_MOVE_BLACK[i] * (where * (-1));
		moveData.push_back(party(CAN_MOVE_WHITE[i], CAN_MOVE_BLACK[i]));
		if (true == MoveNext(moveData, isChecked, where * (-1), testLeft, testRight))
			return true;
		moveData.pop_back();
	}
	isChecked[Parse(left, right, where)] = false;
	return false;
}

int main()
{
	//// 초기화 ////
	party left;
	party right;
	left.white = 3;
	left.black = 3;
	right.white = 0;
	right.black = 0;

	vector<party> moveData;
	map<int, bool> isChecked;
	MoveNext(moveData, isChecked, -1, left, right);

	if (0 == moveData.size())
		cout << "No Solution." << endl;
	for (register int i = 0; i < (int)moveData.size(); ++i)
		cout << "식인종 : " << moveData[i].white << "명 이동, 선교사 : " << moveData[i].black << "명 이동 " << endl;

	return 0;
}