고급 알고리즘
김진홍
<목사와 식인종
문제> 풀이 보고서
1. 목사와 식인종 직접 풀이
‘목사와 식인종’ 문제를 손으로 풀어보면, 아래의 11 단계로 해결되는것을 알 수 있다.
|
대상 |
방향 |
|
식인종 2 |
® |
|
식인종 1 |
¬ |
|
식인종 2 |
® |
|
식인종 1 |
¬ |
|
목사 2 |
® |
|
목사 1 식인종 1 |
¬ |
|
목사 2 |
® |
|
식인종 1 |
¬ |
|
식인종 2 |
® |
|
식인종 1 |
¬ |
|
식인종 2 |
® |
위의 단계를 분석해 본 결과 아래 테이블과 같이 크게 3가지의 형태로 구분할 수 있었다.
|
형태 |
형태번호 |
대상 |
방향 |
|
식인종을 모두 ® 로 옮김 |
1 |
식인종 2 |
® |
|
식인종 1 |
¬ |
||
|
식인종 2 |
® |
||
|
돌아오기 |
|
식인종 1 |
¬ |
|
목사를 모두 ®로 옮김 (안전하게) |
2 |
목사 2 |
® |
|
목사 1 식인종 1 |
¬ |
||
|
목사 2 |
® |
||
|
돌아오기 |
|
식인종 1 |
¬ |
|
식인종을 모두 ®로 옮김 |
3 |
식인종 2 |
® |
|
식인종 1 |
¬ |
||
|
식인종 2 |
® |
위와 같이 3가지의 형태로 구분이 되며 그 중에 형태번호 1과 형태번호 3은 동일한 형태임을 알 수 있다. 그러므로 서로다른 형태는 실제로 두 가지가 되며, 그것은 식인종을 모두 옮기는 과정(형태)과 목사를 모두 옮기는 과정 뿐이게 된다.
2. 초기 이동 대상 선택
처음 시작에서 우리는 목사나 식인종 둘 중에 한명을 옮기거나 목사와 식인종 둘을 옮길 수 있다. 하지만 목사를 옮기면 남아있는 목사의 수가 식인종 수 보다 줄게 됨으로 이것은 불가능하다. 목사와 식인종 둘을 옮기면, 다시 배를 가지고 올때 목사의 안전을 위해 식인종에 돌아가서는 안되므로 반드시 목사가 돌아가야 하는데, 이때의 결과는 결국 식인종 한명만이 강건너로 옮겨진것 뿐이다.
결국 처음 시작에서 목사와 식인종을 옮겨 목사가 돌아오는것과 식인종 둘이 이동해 식인종 한명이 돌아오는것과 결과가 같다. 여기서는 식인종 둘을 먼저 옮기는것을 처음으로 선택하겠다.
3. 규칙
3.1 대상 이동을 위한 형태(패턴)
대상이 이동하기 위해 ‘배’ 라는 수단을 사용하고 있으며 남아있는 사람들을 위해 배를 돌여 보내야 하므로 최소한 한명은 돌아와야 한다.
그렇다면 이동하려는 대상의 수가 돌아오는 수보다 많아야 한다. 배가 수용할 수 있는 인원 수는 최대 두 명이므로 건너갈때에는 두명이, 돌아올때는 한명이 이동해야 결과적으로 모두 건너가게 된다. 그러므로 식인종이 옮겨가려면 갈때 두명, 올때 한명이 오면 된다.
목사는 위의 ‘초기 이동 대상 선택’에 따라 반드시 식인종이 모두 옮겨진 다음, 그리고 식인종 하나가 배를 가지고 돌아온 후 (결국 건너간건 식인종 두명)에 움직일 수 있다.
그리고 목사의 수가 항상 식인종의 수 이상이어야 하므로 건너갈때에는 두명이 갈 수 있지만 돌아올때 양 강변의 목사수가 식인종 수 이상일 수 있도록 고려해야 한다.
양 강변의 목사와 식인종 수의 비율을 맞추어야 하므로 돌아갈때 목사와 식인종 각각 한명씩 모두 두명이 배를 타고 돌아와야 한다. 다시말하면, 위에서 언급한것처럼, 대상이 이동하려면 보낼때는 두명, 돌아올때는 한명이 돌아와야 이동이 이루어진다. 그리고 여기서는 양 강변의 사람 수 비율까지 맞추어야 하므로 돌아올때 목사 한명과 식인종 한명이 돌아와야 안전한 이동이 성립된다.
3.2 규칙 생성
3.1을 정리하면 아래의 과정이 나온다.
(1) 식인종을 모두 먼저 옮기고, 목사를 모두 옮긴다.
(2) 대상을 옮기려면 보낼때 두명, 배를가지고 돌아올때 한명이 필요하다.
(3) 식인종을 옮길때는 보낼때 식인종 둘, 돌아올때 식인종 하나여야 한다.
(4) 목사를 옮길때는 보낼때 목사 둘, 돌아올때 목사 하나 식인종 하나씩이어야
한다.
위의 과정 중 (4)를 보면 돌아올때 목사와 식인종 하나씩이지만, 목사가 모두 이동된 후에는 목사가 돌아가서는 안되므로 (건너편에 남아 있는 식인종이 더 많게 되므로), 그때에는 식인종 한명만을 돌려보낸다. 이 과정을 (4)에 추가한다.
(4) 목사를 옮길때는 보낼때 목사 둘, 돌아올때 목사 하나 식인종 하나씩이어야
한다.
목사를 모두 옮겼으면 식인종 한명만 돌려보낸다.
식인종을 모두 옮기는 과정과 목사를 모두 옮기는 과정을 두개의 step으로 보자.
|
Step 1: 식인종을 모두 옮겨라. Step 2: 목사를 모두 옮겨라. |
Step 1은 ‘과정’ 중 (3)번을 이용하고, Step 2는 (4)번을 이용한다.
|
Step 1: 식인종을 모두 옮겨라. 보낼때: 식인종 2, 돌아올때: 식인종 1 Step 2: 목사를 모두 옮겨라. 보낼때: 목사 2, 돌아올때: 목사 1 식인종 1, 혹은 식인종 1 |
우리는 목사를 모두 옮긴후 식인종을 최종적으로 모두 옮기면 문제가 해결되는것을 알 수 있으므로 Step 1에는 해결시 종료하는 조건을 추가해야 한다.
그리고 두 Step을 상태에 맞추어 번갈아 수행해야 하는데 Step을 전환하는 조건은 이렇다.
Step 1에서는 식인종이 모두 옮겨졌을때 Step 2로 이동한다.
Step 2에서는 목사가 모두 옮겨지는 순간 Step 1으로 이동한다.
이와 같은 조건을 추가해 완성된 규칙은 아래와 같다.
|
Step 1: 식인종을 모두 옮겨라. 보낼때: 식인종 2, 돌아올때: 식인종 1 만약, 목사와 식인종이 모두 옮겨졌으면 종료. 만약, 식인종이 모두 옮겨지면 Step 2로. Step 2: 목사를 모두 옮겨라. 보낼때: 목사 2, 돌아올때: 목사 1 식인종 1, 혹은 식인종 1 만약, 목사가 모두 옮겨졌으면 Step 1로. |
위의 규칙을 psuedo code로 구현하면 아래와 같다.
|
dir ¬ 오른쪽; step ¬ 1; loop { if step == 1, { if dir == 오른쪽, 식인종 2을 dir방향으로; if dir == 왼쪽, 식인종 1을 dir방향으로; if 목사와 식인종 모두 옮겨졌으면, 종료; if 식인종이 모두 도착하면, step ¬ 2; } if step == 2, { if dir == 오른쪽, 목사 2을 dir방향으로; if dir == 왼쪽, if 목사가 모두 도착했으면, 식인종 1을 dir방향으로; else, 목사 1 식인종 1을 dir방향으로; if 목사가 모두 도착했으면, step ¬ 1; }
if dir == 오른쪽, dir ¬ 왼쪽; else dir ¬ 오른쪽; } |
------------------ SOURCE --------------------
#include <stdio.h>
#include <conio.h>
#include <windows.h>
typedef struct
{
int
mis;
int
can;
} BANKSTRUCT;
BANKSTRUCT bank[2]; //
left bank, right bank
#define MAX_STEP 2
#define MAX_RULE 2
#define MAX_SIDE 2
#define STEP_DONE 0
#define STEP_GOTO_1 1
#define STEP_GOTO_2 2
#define STEP_CONTINUE 3
// 0: CAN, CAN
// 1: CAN only
// 2: MIS, CAN
// 3: MIS, MIS
// 4: MIS only
char *rule_name[] = {"2 Cannibals",
"1
Cannibal",
"1
Missionary And 1 Cannibal",
"2
Missionaries",
"1
Missionary" };
#define CANCAN 0
#define CAN 1
#define MISCAN 2
#define MISMIS 3
#define MIS 4
int rule_table[MAX_STEP][MAX_RULE][MAX_SIDE] = \
{ {{CANCAN, CAN}, {NULL, NULL}}, {{MISMIS, MISCAN}, {NULL, CAN}} };
int movepeople(int dir, int todo)
{
static
int s, t;
s
= 0;
t
= 1;
if
(dir == 1)
{
s
= 1;
t
= 0;
}
switch(todo)
{
case
0:
if
(bank[s].can < 2)
return
0;
bank[s].can
-= 2; // move can, can
bank[t].can
+= 2;
break;
case
1:
if
(bank[s].can == 0)
return
0;
bank[s].can--; //
move can only
bank[t].can++;
break;
case
2:
if
(bank[s].mis == 0 || bank[s].can == 0)
return
0;
bank[s].mis--; //
move mis, can
bank[t].mis++;
bank[s].can--;
bank[t].can++;
break;
case
3:
if
(bank[s].mis < 2)
return
0;
bank[s].mis
-= 2; // move mis, mis
bank[t].mis
+= 2;
break;
case
4:
if
(bank[s].mis == 0)
return
0;
bank[s].mis--; //
move mis only
bank[t].mis++;
break;
}
return
1;
}
void resetcondition()
{
bank[0].mis
= 3;
bank[0].can
= 3;
bank[1].mis
= 0;
bank[1].can
= 0;
}
int checkstep(int cur_step)
{
if
(cur_step == 0)
{
if
(bank[1].mis == 3 && bank[1].can == 3)
return
STEP_DONE;
if
(bank[1].can == 3)
return
STEP_GOTO_2;
}
if
(cur_step == 1)
{
if
(bank[1].mis == 3)
return
STEP_GOTO_1;
}
return
STEP_CONTINUE;
}
void displaystate(int rule, int dir)
{
static
int step = 0;
int
i;
step++;
printf("---STEP
%d---------------------\n", step);
if
(rule == -1)
{
printf("<Ohmygod>
Simulator\n");
printf("Press
any key to start!\n");
getch();
}
else
printf("Move:
%s %s\n", rule_name[rule],
(dir
== 0) ? "To The Right" : "To The Left");
for
(i=0; i<3; i++)
{
if
(i < bank[0].mis)
printf("
Mis");
printf("\t\t\t");
if
(i < bank[1].mis)
printf("
Mis");
printf("\n");
}
for
(i=0; i<3; i++)
{
if
(i < bank[0].can)
printf("
Can");
printf("\t\t\t");
if
(i < bank[1].can)
printf("
Can");
printf("\n");
}
Sleep(2000);
}
void ohmygod()
{
int
step = 0;
int
dir = 0; //
left to right
int
cs;
int
stop = 0;
int
rule;
while
(!stop)
{
rule
= 0;
if
(!movepeople(dir, rule_table[step][rule][dir]))
{
rule
= 1;
movepeople(dir,
rule_table[step][rule][dir]);
}
cs
= checkstep(step);
switch(cs)
{
case
STEP_DONE:
stop
= 1;
break;
case
STEP_GOTO_1:
step
= 0;
break;
case
STEP_GOTO_2:
step
= 1;
break;
case
STEP_CONTINUE:
break;
}
displaystate(rule,
dir);
//
turn the direction
dir
= (dir == 0) ? 1:0;
}
}
void main()
{
resetcondition();
displaystate(-1,
-1);
ohmygod();
printf("Done!\n");
}