[알고리즘 수학] 물병 세개

물로 가득 찬 8L 짜리 물병 한개가 비어 있고 비어 있는 5L,3L 물병이 각각 하나씩 있다.

이 셋 중 어느 물통에든 정확히 물 4L를 담는 방법을 설명하라.

물은 이 세개의 물통을 이용할 수만 있으며 물을 옮겨 담을 때는 원래 물이 들어 있던 통이 완전히 비거나 물이 담기는 통이 가득 찰 때까지 옮겨 담아야 한다.

[문제 출처] 길벗 - 알고리즘 퍼즐

 

[문제풀이] 이러한 유형의 문제는 정보올림피아드 예선 문제에서 자주 출제되던 유형의 문제이다.

풀이 방법은 다음과 같다.

8L짜리 물병에서 5L 에 가득 채우는 방법(8L/3L,5L/5L,3L/0L)와 3L에 가득 채우는 방법(8L/5L,5L/0L,3L/3L) 두가지 방법이 존재한다.

이 것을 다음과 같이 각각 또 분배를 할 수 있다.

8L/3L,5L/5L,3L/0L - 8L/0L,5L/5L,3L/3L(8L->3L), 8L/3L,5L/2L,3L/3L(5L->3L)

8L/5L,5L/0L,3L/3L - 8L/0L,5L/5L,3L/3L(8L->5L)(X),8L/5L,5L/3L,3L/0L(3L->5L) =>(X)는 이미 위에서 처리 된 경우임

==========

8L/0L,5L/5L,3L/3L - 8L/5L,5L/0L,3L/3L(5L->8L)(X),8L/3L,5L/5L,3L/0L(3L->8L)(X) 

8L/3L,5L/2L,3L/3L - 8L/0L,5L/5L,3L/3L(8L->5L)(X),8L/6L,5L/2L,3L/0L(3L->8L),8L/3L,5L/5L,3L/0L(3L->5L)(X)

8L/5L,5L/3L,3L/0L - 8L/3L,5L/5L,3L/0L(8L->5L)(X),8L/2L,5L/3L,3L/3L(8L->3L),8L/5L,5L/0L,3L/3L(5L-3L)(X)

==========

8L/6L,5L/2L,3L/0L - 8L/3L,5L/5L,3L/0L(8L->5L)(X),8L/3L,5L/2L,3L/3L(8L->3L)(X),8L/8L,5L/0L,3L/0L(5L->8L)(X),8L/6L,5L/0L,3L/2L(5L->3L)

8L/2L,5L/3L,3L/3L -> 8L/0L,5L/5L,3L/3L(8L->5L)(X) , 8L/5L,5L/0L,3L/3L(5L->8L)(X),8L/5L,5L/3L,3L/0L(3L->5L)(X)

==========

8L/6L,5L/0L,3L/2L - 8L/1L,5L/5L,3L/2L(8L->5L),8L/5L,5L/0L,3L/3L(8L->3L)(X),8L/8L,5L/0L,3L/0L(3L->8L)(X),8L/6L,5L/2L,3L/0L(3L->5L)(X)

==========

8L/1L,5L/5L,3L/2L - 8L/0L,5L/5L,3L/3L(8L->3L)(X),8L/6L,5L/0L,3L/2L(5L->8L)(X),8L/1L,5L/4L,3L/3L(5L->3L) (여기에서 4L 발생함)

따라서 역으로 빨간색을 따라 가면 다음과 같이 나오는 것을 알 수 있다.

8L->5L (3,5,0)

5L->3L(3,2,3)

3L->8L(6,2,0)

5L->3L(6,0,2)

8L->5L(1,5,2)

5L->3L(1,4,3)

 

이러한 풀이 방법은 프로그램 알고리즘 기법 중 DFS(깊이우선탐색) 또는 BFS(넓이우선탐색) 방법으로 현재 상태에서 그 다음 상태가 될 수 있는 모든 방법을 기술 하고 이전에 찾아 보았던 방법은 제거하면서 정답이 나올때까지 진행을 하면 된다.

정답을 찾으면 역으로 어떤 루트에 의해 나왔는지 경로를 찾아서 출력하면 된다.

이러한 유형의 문제는 정보올림피아드 2010년 이전에는 필기 유형으로 많이 나왔으며 2010년 이후에는 실기유형으로 코딩을 하는 유형으로 많이 출제 되었던 유형이다.