[알고리즘 퍼즐] 독살 음모를 밝혀라! 독이 든 와인 찾기

문제

왕이 마실 와인 8병 중 하나에 강력한 독이 들어 있다. 한 방울만이라도 치명적이다.

정상 와인을 아무리 섞어도 치명적이다. 다행히 검사장비를 구할 수 있다.

단, 검사는 1시간이 필요하다. 왕은 무조건 1시간 후에 와인을 마실테니 독이 든 병을 찾아내라는 명령을 내렸다.

이를 위해, 몇 대의 검사 장비가 있으면 충분할까? (한 번 검사할 때에는 여러 병의 와인을 섞어 검사가 가능하다.)

 

풀이

와인 8병을 검사하는데 최소한의 검사 장비로 해결해야하는 문제입니다.

8병의 와인이지만 사실 7병만 검사하면 충분합니다. (모두 독이 안들어있으면 검사안한 병에 독이 있으니까요.)

 

최대 7대의 검사 장비가 있으면 편하지만, 최소한의 검사 장비로 하는 것이 중요하기 때문에 다음과 같이 생각했습니다.

와인을 일자로도 세워보고 원으로도 세워보면서 어떻게 검사해야 효율적일지 고민했습니다.

제가 고민했을때는 4대가 한계였습니다. 그리고 다음과 같이 결론을 내렸습니다.

 

1,2번 /  3,4번 / 5,6번 / 1,3,5,7번을 검사하는 것입니다.

편의상 순서대로 A, B, C, D 검사기라고 했을때, 

 

A,D 검사기에서 독이 검출되면 1번에 독이 있는 것입니다.

A에서 독이 검출되고 D에서 검출되지 않았다면 2번에 독이 있는 것입니다.

같은 논리로 B, D / C, D 검사기를 돌려서 검출하는 것입니다.

A,B,C에서 독이 검출되지 않고 D에서 검출되었다면 7번에 독이 있는 것입니다.

A,B,C,D 검사기 모두 독이 검출되지 않는다면 8번에 독이 있는 것입니다.

 

위의 내용을 코드로 구현해보겠습니다.

 

코드

파이썬을 이용해서 구현했습니다.

 

기본 설정

▲ 와인에 독을 넣는 과정(?)

우선 와인 8병을 배열의 형태로 선언했습니다.

랜덤으로 한 병을 골라서 독이 들어 있는 와인을 추가합니다.

0은 독이 없는 것이고, 1은 독이 들어있는 것을 의미합니다.

 

검사기 설정

▲ 검사기 세팅하는 과정

검사기를 설정하는 과정입니다.

위에서 말로 설명할때는 1번째부터 셌지만, 인덱스는 0번부터이기 때문에 위와 같이 설정합니다.

 

독 검출

▲ 독이 들어있는 와인을 찾는 과정

if ···· elif ···· else 문으로 나타냈습니다.

검사기도 배열에 넣고 반복문을 돌려서 찾을까도 생각해봤지만, 기본 연산 횟수가 더 늘고 가독성이 떨어져서 일일히 표현했습니다. (기본 연산 횟수가 늘어난다는 것은 알고리즘 수행시간이 늘어난다는 뜻입니다.)

 

결과

제대로 검사가 되었는지 확인하기 위해서 마지막에 어느 병에 독이 들어있는지 출력합니다.

결과가 제대로 나오는지 출력해보겠습니다.

▲ 결과1

▲ 결과2

보시는 것처럼 제대로 검출되는 것을 확인할 수 있습니다.

4대의 검사기로 왕은 독이 든 와인을 먹지 않게 되었습니다!

 

정리

간단한 알고리즘 문제를 풀어보았습니다. 이게 최적의 답안은 아닐 수도 있습니다.

더 좋은 방법이 있다면 댓글 남겨주세요!