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

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

### 설명 ¶

• 전형적인 다해보기..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;
}
```