[C++] 5월 16일 코딩 테스트 수업

배추, 양, 늑대, 농부 문제

#pragma once

#include <stdio.h>

class C_CROSS
{
private:
	enum class E_LAND
	{
		E_NONE = 0,
		E_VISIT,
		E_END
	};
	enum 
	{
		E_NONE,
		E_CABBAGE =		0x01,
		E_SHEEP	  =		0x02,
		E_WOLF	  =		0x04,
		E_FARMER  =		0x08,
	};
private:
	bool	m_arEnable[16];
	E_LAND	m_arVisit[2][16];

private:
	void cross(int nState, bool bLeft, int nDepth);
	void print(int nState, int nDepth);

public:
	C_CROSS() = default;
	void init();
	void run();
};

 

#include "cross.h"

void C_CROSS::init()
{
	for (int i = 0; i < 16; i++)
	{
		m_arEnable[i] = true;
	}
	m_arEnable[E_SHEEP | E_CABBAGE] = false;
	m_arEnable[E_SHEEP | E_WOLF] = false;
	m_arEnable[E_SHEEP | E_WOLF | E_CABBAGE] = false;

	m_arVisit[0][E_CABBAGE | E_SHEEP | E_WOLF | E_FARMER] = E_LAND::E_END;
}

void C_CROSS::run()
{
	cross(E_CABBAGE | E_SHEEP | E_WOLF | E_FARMER, true, 0);
}

void C_CROSS::cross(int nState, bool bLeft, int nDepth)
{
	// 방문한적 있으면 실패
	if (m_arVisit[(int)bLeft][nState] == E_LAND::E_VISIT)
	{
		printf("실패\n");
		return;
	}

	if (m_arVisit[(int)bLeft][nState] == E_LAND::E_END)
	{
		// 도착했으면 종료 - 결과 출력

		printf("성공 : %d ", bLeft);
		print(nState, nDepth);
		return;
	}

	m_arVisit[bLeft][nState] = E_LAND::E_VISIT;
	
	// 반대편 땅
	int nAnother = ~nState & 15;

	for (int i = 0; i < 4; i++) 
	{
		int nObject = E_CABBAGE << i;
		int nMove = nObject | E_FARMER;

		//object가 있는지 없는지 체크
		if (nObject & nState && m_arEnable[nState ^ nMove])
		{
			printf("%d ", bLeft);
			printf("이동 -> ");
			print(nMove, nDepth);
		    //nMove를 기존값에서 제거했을때 가능여부
			cross(nAnother | nMove, !bLeft, nDepth + 1);
		}
	}
	m_arVisit[bLeft][nState] = E_LAND::E_NONE;
    // 이거 없으면 다시 나와서 돌아가지를 못해서 값이 2개가 나오지 못함 
}

void C_CROSS::print(int nState, int nDepth)
{
	if (nState	& E_CABBAGE)
		printf("양배추 ");
	if (nState & E_SHEEP)
		printf("양 ");
	if (nState & E_WOLF)
		printf("늑대 ");
	if (nState & E_FARMER)
		printf("농부 ");

	printf(": %d \n", nDepth);
}

 

#include <iostream>
#include "cross.h"

int main()
{
	C_CROSS cCross{};

	cCross.init();
	cCross.run();

}