설명

  • 전형적인 다해보기..OTL.ㅋ
    • 대충짜느라 별로 생각해보지는 않았지만.. 다해보는 방법 외에 또 무언가 존재할지도..?

    소스


    ~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;
    }
    
    Retrieved from http://wiki.zeropage.org/wiki.php/식인종과선교사문제/조현태
    last modified 2021-02-07 05:30:18