[알고리즘 수학]강건너기 문제

어떤 사람이 늑대 한마리, 염소 한마리, 양배추 한통을 가지고 강둑에 서 있다.

이 셋을 모두 배로 반대편으로 옮겨야 한다.

하지만 배에는 이 사람 외에는 하나만 실을 수 있다.

그 가 없으면 늑대는 염소를 먹어 버리고 염소는 양배추를 먹어 버린다.

 

여기서 퀴즈

늑대가 염소를 잡아먹지 못하고 또 염소가 양배추를 먹지 못하게 하면서 모두를 건너편 강가로 데려 갈 수 있을까?

 

힌트

사소한 예외 하나를 빼면 이 퀴즈는 각 상황에서 옮길 수 있는 유일한 것을 열거하는 방식을 풀 수 있다.

 

정답

풀이1)

1. 염소를 데리고 강을 건넌다.(염소/늑대,양배추)

2. 염소를 내려 놓고 다시 건너와서 늑대를 데리고 강을 건넌다.

3. 늑대를 내려 놓고 염소를 데리고 다시 건너온다.(늑대/염소,양배추)

4. 양배추를 데리고 강을 건넌 후 양배추를 내려 놓는다.(늑대,양배추/염소)

5. 마지막으로 다시 건너와서 염소를 데리고 건너가면 된다.

풀이2)

풀이 1에서 늑대 대신 양배추를 데리고 건너는 방법도 동일하다.

 

컴퓨팅 사고력

컴퓨팅 알고리즘 문제해결 방법에 변환정복(transform-and-conquer)이라는 문제 해결 방법이 있다. 변환정복에서는 문제를 두 단계에 걸쳐 푼다. 첫번째는 변환 단계로 주어진 문제를 어떤 이유로든 더 풀기 쉬운 다른 문제로 변형하거나 변환한다. 두번째는 정복 단계로 이 단계에서 실제로 문제를 해결한다. 이 문제와 같은 경우 상태 공간 그래프로 문제를 변형 후에 다음 이동 상태를 현재 위치를 기준으로 문제를 해결해 나갈 수 있다. [참고] 알고리즘 퍼즐

 

유사한 문제)

선교사와 식인종 - https://wondangcom.tistory.com/1791

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

강건너기 - https://blog.naver.com/icon003/221329120814

2003년 정보올림피아드 중고등 예선 14 - 강건너기

강건너기 - https://blog.naver.com/icon003/221713727358

2019년 정보올림피아드 중등부(유형1) -문제4