강의자료/알고리즘 수학

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

원당컴1 2022. 8. 26. 12:17

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

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

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

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

 

여기서 퀴즈

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

 

힌트

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

 

정답

더보기

풀이1)

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

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

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

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

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

풀이2)

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

 

컴퓨팅 사고력

컴퓨팅 알고리즘 문제해결 방법에 변환정복(transform-and-conquer)이라는 문제 해결 방법이 있다.
변환정복에서는 문제를 두 단계에 걸쳐 푼다.

첫번째는 변환 단계로 주어진 문제를 어떤 이유로든 더 풀기 쉬운 다른 문제로 변형하거나 변환한다.
두번째는 정복 단계로 이 단계에서 실제로 문제를 해결한다.

이 문제와 같은 경우 상태 공간 그래프로 문제를 변형 후에 다음 이동 상태를 현재 위치를 기준으로 문제를 해결해 나갈 수 있다.

[참고] 알고리즘 퍼즐

 

유사한 문제)

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

 

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

세명의 선교사와 세명의 식인종이 강의 건너편에 있습니다. 현재 강을 건너와야 하는데 건너편에는 2인용 나룻배 하나만 있습니다. 만약 강의 어느 한쪽이라도 식인종 수가 선교사의 수보다 많

wondangcom.com

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

 

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

문제풀이) 배가 한척이고 최대 두사람이 탈 수 있는데 갑1분,을2분,병5분,정10분이 걸린다. 따라서 갑(1),...

blog.naver.com

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

 

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

정답) 80 문제풀이) 0회 어린이는 반대쪽 2, 이쪽 0 1회 반대편에서 1명의 어린이가 이쪽으로 오면 어린이...

blog.naver.com

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기