[컴퓨팅 사고력] 선교사와 식인종

세명의 선교사와 세명의 식인종이 강의 건너편에 있습니다. 현재 강을 건너와야 하는데 건너편에는 2인용 나룻배 하나만 있습니다. 만약 강의 어느 한쪽이라도 식인종 수가 선교사의 수보다 많으면 식인종들은 선교사를 잡아 먹습니다. 선교사들이 잡아 먹히지 않고 6명 모두 무사히 강을 건너는 방법을 선교사들에게 설명해 주세요.

 

문제풀이)

(강건너선교사수,강건너식인종수,이쪽선교사수,이쪽 식인종수) 와 같은 형태로 생각해 보면

(3,3,0,0) 에서 가능한 경우는 (2,2,1,1) 이다.

(2,2,1,1) 에서 보트를 가지고 선교사가 강을 건너간다면 (3,2,0,1) 이 된다.

(3,2,0,1) 에서 선교사가 이동하는 순간 잡아 먹히므로 이때는 식인종 둘만 이동하는 경우 밖에 없다. 따라서 (3,0,0,3)

(3,0,0,3) 에서 식인종 1명이 강을 건너가면 (3,1,0,2) 가 되며 여기서 선교사 둘이 보트를 타고 건너 온다면 (1,1,2,2) 가 된다.

여기서 반대로 식인종 한명이 가던 선교사 한명이 가던 선교사가 잡아먹히므로  이때는 한명의 식인종과 한명의 선교사가 같이 이동하는 경우밖에 없습니다.

따라서 (2,2,1,1) 이고 강건너의 선교사 두명이 강을 건너 오게 되면 (0,2,3,1) 이 됩니다.

다시 나룻배를 가지고 건너가야 하는데 그 경우는 식인종이 가는 방법만 있습니다. 따라서 (0,3,3,0) 이 되며 그 다음은 식인종 2명이 건너오고(0,1,3,2) 다시 식인종 한명이 건너가서(0,2,3,1) 두명이 건너 온다면 (0,0,3,3) 과 같이 이동할 수 있습니다.

 

이러한 문제는 정보올림피아드 예선 문제중에서 다음과 같은 형태로 출제 된적이 있습니다.

(2003년 초등부 14번) 갑, 을, 병, 정 네 사람이 강을 건너려고 한다. 그런데 강에는 배가 한 척밖에 없고, 그 배에는 최대 두 사람이 탈 수 있다. 혼자서 배를 타고 노를 저어 강을 건널 경우 갑은 1분, 을은 2분, 병은 5분, 정은 10분의 시간이 걸린다. 둘이서 함께 배를 탈 경우, 안전을 위해 더 천천히 노를 젖는 사람이 노를 잡는다. (예를 들어 을과 병이 함께 배를 탈 경우, 병이 노를 잡게 되고, 따라서 강을 건너는데 5분이 걸린다.) 네 사람이 무사히 강을 건너려면 최소 몇 분이 걸릴까? 문제풀이) 갑(1),을(2) 가 먼저 건너가서 (2분) 을(2)가 배를 끌고 온다 (4분),병(5분),정(10분)이 건너가서(14분) 갑(1)이 배를 가지고 온다(15분),을(2)을 태우고 건너가면 17분에 건너갈수 있다.

 

 

컴퓨팅사고력

이 문제는 컴퓨터 과학에서 사용하는 알고리즘 중 넓이 우선 탐색과 관련이 있습니다.

처음 (3,3,0,0,1) - (강건너선교사수,강건너식인종수,이쪽선교사수,이쪽식인종수,나룻배의 위치1이면 강건너2이면 이쪽) 에서 출발을 하면

(3,3,0,0,1) - (1,3,2,0,2),(2,2,1,1,2),(3,1,0,2,2) 와 같이 3가지 경우가 있는데 (1,3,2,0,2)는 성립 할 수 없으므로 제거 됩니다.

(2,2,1,1,2) - (3,3,0,0,1),(3,2,0,1,1),(2,3,1,0,1) 와 같이 3가지 경우가 있는데 (3,3,0,0,1)는 좀전에 있던 상태이므로 제거 되고 (2,3,1,0,1)은 불가능하므로 제거되므로 (3,2,0,1,1)인 경우만 남게됩니다.

(3,1,0,2,2) - (3,3,0,0,1),(3,2,0,1,1) 와 같이 2가지 경우가 있는데 (3,3,0,0,1) 은 좀전의 상태이고 (3,2,0,1,1) 는 바로 위에서 남은 상태와 동일합니다.

 

이런 방법으로 현재 자신의 위치에서 갈 수 있는 모든 경우를 찾아 보는 것이 넓이 우선탐색(BFS-Breadth First Search) 이라고 합니다.

 

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원