늑대 한 마리, 염소 한 마리, 양배추 한 개를 갖고 있는 남자가 있었다. 길을 가는 도중에 강이 나타나자 작은 배를 빌렸다. 이 배에는 사람 한 명과 늑대, 염소, 양배추 중의 하나밖에 실을 수 없다. 늑대와 염소를 함께 남겨두면 늑대가 염소를 잡아먹을 것이다. 또 염소와 양배추를 함께 남겨두면 염수가 양배추를 먹어버릴 것이다. 늑대가 염소를 잡아먹지 못하게, 또 염소가 양배추를 먹지 못하게 하면서 모두를 건너편 강가로 데려가려면 어떤 식으로 건나가야 할까? 답은 두가지가 있다. 1. 먼저 염소를 데리고 강을 건넌다. 그런 다음 남은 혼자 다시 돌아와 늑대를 데리고 강을 건넌 후 염소를 데리고 다시 돌아온다. 이번에는 염소를 남겨두고 양배추를 갖고 강을 건넌 다음 혼자서 다시 돌아와 마지막으로 염소를 데리고 건넌다. 2. 염소를 데리고 강을 건넌다. 그리고 남은 혼자 다시 돌아와 양배추를 갖고 강을 건넌다. 그런 다음 염소를 데리고 돌아와 염소는 남겨두고 늑대를 데리고 강을 건넌다. 마지막으로 혼자 다시 돌아와 염소를 데리고 건넌다.
일명 강 건너기 문제입니다. 꽤 오래 전부터 내려온 문제로 비슷하고 변형된 문제가 많이 있습니다. 특별하게 이름 지어지진 않은 것으로 보이지만 강 건너기 (River Crossing Puzzle)로 검색하면 위키백과에서 간단한 설명을 볼 수 있습니다. 위키백과 바로가기 - http://ko.wikipedia.org/wiki/%EA%B0%95_%EA%B1%B4%EB%84%88%EA%B8%B0_%ED%8D%BC%EC%A6%90 여기서는 가장 오래된 강 건너기 퍼즐 중 ‘선교자와 식인종 문제’와 변형되어 좀 더 어려워진 ‘조련사, 식인종, 드라큐라 가족 문제’를 다루겠습니다. ‘선교자와 식인종 문제’ 문제) 선교사 세 명과 식인종 세 명이 강을 건너려고 한다. 강의 어느 쪽이든 선교사보다 식인종의 수가 많게 되면 식인종은 선교사를 해친다. 그러나 선교사와 식인종의 수가 같거나 선교사가 많으면 아무도 해치지 않는다. 한 번에 두 사람만 보트에 탈 수 있다고 할 때, 여섯 사람이 무사히 강을 건너도록 해야 한다. 풀이) ‘조련사, 식인종, 드라큐라 가족 문제’ 위 문제의 경우 ‘선교사와 식인종 문제’보다 조금 더 복잡하며 문제 자체는 같으나 등장인물이 다른 문제가 많이 있습니다. (웹 검색으로 쉽게 찾을 수 있습니다.) 문제) 강의 한쪽 편에 호랑이와 조련사, 식인종과 그의 아들 2명, 드라큘라와 그의 딸 2명이 있습니다. 다음과 같은 조건이 있을 때 이들은 어떻게 강을 건너야 할까요? 조건) 강을 건너기 위해서는 반드시 배를 이용해야하며 한 번에 최대 2명(또는 동물 1마리, 사람 1명)만 탈 수 있습니다. 단, 아이들끼리만 배에 탈 수 없으며 조련사, 식인종, 드라큘라와 동행해야 합니다. (즉, 아들 1명과 딸 1명, 아들 2명, 딸 2명과 같은 조합으로 배에 탑승할 수 없습니다.) 호랑이는 조련사가 없으면 다른 사람들을 잡아먹습니다. 식인종은 드라큘라가 없으면 드라큘라의 딸을 해칩니다. 드라큘라는 식인종이 없으면 식인종의 아들을 해칩니다. 풀이) 어떤 사람이 늑대 한마리, 염소 한마리, 양배추 한통을 가지고 강둑에 서 있다. 이 셋을 모두 배로 반대편으로 옮겨야 한다. 하지만 배에는 이 사람 외에는 하나만 실을 수 있다. 그 가 없으면 늑대는 염소를 먹어 버리고 염소는 양배추를 먹어 버린다. 여기서 퀴즈 늑대가 염소를 잡아먹지 못하고 또 염소가 양배추를 먹지 못하게 하면서 모두를 건너편 강가로 데려 갈 수 있을까? 힌트 사소한 예외 하나를 빼면 이 퀴즈는 각 상황에서 옮길 수 있는 유일한 것을 열거하는 방식을 풀 수 있다. 정답 더보기 풀이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 |
강건너기 문제 답 - gang-geonneogi munje dab
관련 게시물
저작권 © 2024 ko.ketiadaan Inc.
