농부, 배추, 염소, 늑대 강건너기

(해당글은 완성된글이 아닙니다)

 

문제

농부, 염소, 배추, 늑대가 강의 오른편에있다

배를 이용하여 강의 왼편으로 건너야한다

항상 농부가 타야한다

늑대나 염소 배추 중에서 한개만 실을수 있으며 동시에 다수를 실을순없다

농부가 없을때는 늑대가 염소를 염소는 배추를 먹어버린다

 

 

푸는방식 : DFS를 통하여 Stack을 사용하여 경우의 수를 저장하고

마지막으로 넣은값을 확인하고 해당값이 잘못된값이면 스택에서 값을 되돌려

아직 빼지않은 경우의 수를 다시 확인해본다

 

 

 

비트연산자로 표기한다

32 16 8 4 2 1 일테니

0x01, 0x02, 0x04, 0x08 

2 ^ 4 = 16

16 -> 0x10 ㅠ

 

코드가 아직 수정중입니다

#include <iostream>
#include <stdio.h>
#include <set>

using namespace std;
set<int> m_arVisited;

class C_GAME
{
public:
	enum 
	{
		E_CABBAGE	= 0x01,
		E_GOAT		= 0x02,
		E_FARMER	= 0x04,
		E_WOLF		= 0x08,
		E_MAX		= 0x10
	};
	
};
//오른쪽땅 (1) |  왼쪽땅 (0)
bool bCrossSuccess(int nData)
{
	//존재해야하며 전부 왼쪽 0 일때 성공 XOR
	int bitMask = C_GAME::E_CABBAGE | C_GAME::E_GOAT | C_GAME::E_FARMER | C_GAME::E_WOLF;
	return (nData & bitMask) == 0;
}

bool bValidSituation(int nData)
{
	bool s_CABBAGE	= (nData & C_GAME::E_CABBAGE) != 0;
	bool s_GOAT = (nData & C_GAME::E_GOAT) != 0;
	bool s_Farmer = (nData & C_GAME::E_FARMER) != 0;
	bool s_Wolf = (nData & C_GAME::E_WOLF) != 0;

	//농부가 없으면( 늑대 -> 염소 x) (염소 -> 배추 x)
	if (!s_Farmer)
	{
		if (s_Wolf == s_GOAT)
			return false;
		if (s_GOAT == s_CABBAGE)
			return false;
	}
	return true;
}
int DFS(int nData)
{
	if (m_arVisited.count(nData))
		return -1;
	m_arVisited.insert(nData);

	if (bCrossSuccess(nData))
	{
		printf("강 건너기 성공\n" );
		return 0;
	}

	//농부 왼 오른쪽 체크
	bool pos_Farmer = (nData & C_GAME::E_FARMER) != 0;

	int next = nData ^ C_GAME::E_FARMER;
	if (bValidSituation(next))
	{
		int result = DFS(next);
		if (result != -1)
			return result + 1;
	}
	//농부 + 늑대 경우
	if (((nData & C_GAME::E_WOLF) != 0) == pos_Farmer)
	{
		int nextWolf = nData ^ (C_GAME::E_FARMER | C_GAME::E_WOLF);
		if (bValidSituation(nextWolf))
		{
			int result = DFS(nextWolf);
			if (result != -1)
				return result + 1;
		}
	}
	//농부 + 염소 경우
	if (((nData & C_GAME::E_GOAT) != 0) == pos_Farmer)
	{
		int nextGoat = nData ^ (C_GAME::E_FARMER | C_GAME::E_GOAT);
		if (bValidSituation(nextGoat))
		{
			int result = DFS(nextGoat);
			if (result != -1)
				return result + 1;
		}
	}
	//농부 + 배추 경우
	if (((nData & C_GAME::E_CABBAGE) != 0) == pos_Farmer)
	{
		int nextCabbage = nData ^ (C_GAME::E_FARMER | C_GAME::E_CABBAGE);
		if (bValidSituation(nextCabbage))
		{
			int result = DFS(nextCabbage);
			if (result != -1)
				return result + 1;
		}
	}
	return -1;
}
int main()
{
	// 초기 상태: 모두 오른쪽 강가 (비트가 1이면 오른쪽)
	int startState = C_GAME::E_CABBAGE | C_GAME::E_GOAT | C_GAME::E_FARMER | C_GAME::E_WOLF;

	int result = DFS(startState);

	if (result != -1)
		printf("총 이동 횟수: %d\n", result);
	else
		printf("강을 건널 수 없습니다.\n");

	return 0;
}

 

 

참고)

https://blog.naver.com/rlaalsdn456456/221676020039

농부, 배추, 염소, 늑대 강건너기 - DFS (파이썬)