View source for 식인종과선교사문제/변형진

= 주저리 =
이 문제를 푸는데 흔히 이용되는 Backtracking 기법을 사용하지 않고 구현하는 방법이 없을까 해서, Case-by-case로 최소한의 상황에 대한 처리 방법을 지정해보았다.
가능한 모든 cases를 분석한 결과 우로 건너기와 좌로 건너기에서 각각 상황에 따라 3가지 건너기 방법이 사용될 수 있었다.

'''그러나 여기에서 사용한 방법은 모든 cases를 사람이 직접 조건 별로 분류해 주어야 하므로 결코 좋은 방법이 아니다.'''

여기서는 구현하지 않았지만, 모든 cases에 대해 각각 어떻게 처리할 수 있는지를 먼저 컴퓨터가 계산하여 DB에 담아서 일괄 처리하면, 이 문제가 상당히 복잡해질 경우 Backtracking보다 나은 효율을 보일 수도 있지 않을지?

= 소스코드 =
 &lt;?
 $s = new survive();
 $s-&gt;to_right();
 class survive
 {
 	var $left, $right;
 	function __construct()
 	{
 		$this-&gt;left = array("canni" =&gt; 3, "missi" =&gt; 3);
 		$this-&gt;right = array("canni" =&gt; 0, "missi" =&gt; 0);
 	}
 	function to_right()
 	{
 		if($this-&gt;left[canni]==$this-&gt;left[missi]&amp;&amp;$this-&gt;left[canni]==3) $this-&gt;ferry(1,1);
 		elseif($this-&gt;left[canni]&lt;&gt;$this-&gt;left[missi]&amp;&amp;$this-&gt;left[canni]&gt;1) $this-&gt;ferry(2,0);
 		else $this-&gt;ferry(0,2);
 		$this-&gt;to_left();
 	}
 	function to_left()
 	{
 		if($this-&gt;right[canni]==$this-&gt;right[missi]&amp;&amp;$this-&gt;right[canni]==2) $this-&gt;ferry(-1,-1);
 		elseif($this-&gt;right[canni]==$this-&gt;right[missi]) $this-&gt;ferry(0,-1);
 		else $this-&gt;ferry(-1,0);
 		$this-&gt;to_right();
 	}
 	function ferry($canni, $missi)
 	{
 		if($canni&gt;=0&amp;&amp;$missi&gt;=0) echo "우측 식인종 {$this-&gt;right[canni]}+$canni, 선교사 {$this-&gt;right[missi]}+$missi&lt;br&gt;";
 		elseif($canni&lt;=0&amp;&amp;$missi&lt;=0) echo "좌측 식인종 {$this-&gt;left[canni]}+".(-$canni).", 선교사 {$this-&gt;left[missi]}+".(-$missi)."&lt;br&gt;";
 		else die("에러: $canni, $missi");
 		$this-&gt;left[canni] -= $canni; $this-&gt;left[missi] -= $missi;
 		$this-&gt;right[canni] += $canni; $this-&gt;right[missi] += $missi;
 		if(!$this-&gt;left[canni]&amp;&amp;!$this-&gt;left[missi]) exit();
 	}
 }
 ?&gt;


== thread == 

* 모든 케이스를 DB에 저장해서 푸는것과 비슷하게 머신러닝으로 학습시켜 풀게 만들면(문제 해결에 관한 state를 저장했다가 푸는것이므로 유사하다고 생각했습니다) 정답률이 얼마나 나올까요? - [[bluemir]]


----
[[식인종과선교사문제]]