주저리 ¶
이 문제를 푸는데 흔히 이용되는 Backtracking 기법을 사용하지 않고 구현하는 방법이 없을까 해서, Case-by-case로 최소한의 상황에 대한 처리 방법을 지정해보았다.
가능한 모든 cases를 분석한 결과 우로 건너기와 좌로 건너기에서 각각 상황에 따라 3가지 건너기 방법이 사용될 수 있었다.
가능한 모든 cases를 분석한 결과 우로 건너기와 좌로 건너기에서 각각 상황에 따라 3가지 건너기 방법이 사용될 수 있었다.
그러나 여기에서 사용한 방법은 모든 cases를 사람이 직접 조건 별로 분류해 주어야 하므로 결코 좋은 방법이 아니다.
여기서는 구현하지 않았지만, 모든 cases에 대해 각각 어떻게 처리할 수 있는지를 먼저 컴퓨터가 계산하여 DB에 담아서 일괄 처리하면, 이 문제가 상당히 복잡해질 경우 Backtracking보다 나은 효율을 보일 수도 있지 않을지?
소스코드 ¶
~php <? $s = new survive(); $s->to_right(); class survive { var $left, $right; function __construct() { $this->left = array("canni" => 3, "missi" => 3); $this->right = array("canni" => 0, "missi" => 0); } function to_right() { if($this->left[canni]==$this->left[missi]&&$this->left[canni]==3) $this->ferry(1,1); elseif($this->left[canni]<>$this->left[missi]&&$this->left[canni]>1) $this->ferry(2,0); else $this->ferry(0,2); $this->to_left(); } function to_left() { if($this->right[canni]==$this->right[missi]&&$this->right[canni]==2) $this->ferry(-1,-1); elseif($this->right[canni]==$this->right[missi]) $this->ferry(0,-1); else $this->ferry(-1,0); $this->to_right(); } function ferry($canni, $missi) { if($canni>=0&&$missi>=0) echo "우측 식인종 {$this->right[canni]}+$canni, 선교사 {$this->right[missi]}+$missi<br>"; elseif($canni<=0&&$missi<=0) echo "좌측 식인종 {$this->left[canni]}+".(-$canni).", 선교사 {$this->left[missi]}+".(-$missi)."<br>"; else die("에러: $canni, $missi"); $this->left[canni] -= $canni; $this->left[missi] -= $missi; $this->right[canni] += $canni; $this->right[missi] += $missi; if(!$this->left[canni]&&!$this->left[missi]) exit(); } } ?>