백준 2251
첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구하기
- 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다.
- 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
- 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
- 첫째 줄에 세 정수 A, B, C가 주어진다.
- 첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
입출력
| 입력 | 출력 |
|---|---|
| 8 9 10 | 1 2 8 9 10 |
접근 방식
: dfs/bfs 문제라고 생각을 못했다. 그냥 c를 배열에 먼저 넣고, a또는 b가 c보다 작거나 같다면 넣고, 그 차이를 넣고 중복을 제거하였다. ---> 틀렸습니다.
알게된 점
bfs로 푸는 이유
: 물을 옮길 수 있는 각각의 경우에 대해 탐색하기 위해
x->y, x->z, y->z, y->z, z->x, z->y
물통에 들어있을 수 있는 모든 경우의 수를 찾아서 첫번째 물통이 비어있을 때 세번째 물통의 양을 구한다.
1. 물통이 3개이지만 물의 총량은 고정이므로 a, b 두 물통만 체크하면 된다.
c는 저절로 정해진다.
2. visited 리스트를 2중 리스트로 작성한다.(a, b)
3. 처음에 (0,0)을 넣고 BFS
- a물통이 0일 때 c물통의 양을 리스트(답)에 넣어준다.
- x->y, x->z, y->z, y->z, z->x, z->y 의 6가지를 모두 탐색
- 조건에 맞다면 계속 탐색
- 물통에 들어있는 경우의 수를 구하는 방법
- 물을 옮기는 방법의 수를 찾는다.
(x : a에 담긴 물의 양, y : b에 담긴 물의 양, z : c에 담긴 물의 양)
: x->y, x->z, y->z, y->z, z->x, z->y 의 6가지
water = min(x, b-y): x에서 y로 옮길 물. x 전체를 옮기거나 b물통을 꽉 채운다.(한 물통이 비거나 다른 물통이 가득찰 때까지)pour(x-water, y+water): 옮긴 후의 x와 y상태를 큐에 저장.- c물통에 남아있는 물의 양 : z = c-x-y (물의 총량은 정해져있기 때문)
코드
from collections import deque
def pour(x, y, visited, q):
if visited[x][y] == 0:
visited[x][y] = 1
q.append((x, y))
def bfs(a, b, c, visited):
q = deque()
q.append((0,0))
visited[0][0] = 1
ans = []
while q:
x, y = q.popleft()
z = c-x-y
if x == 0:
ans.append(z)
#x->y
if x>0 and y<b:
water = min(x, b-y)
pour(x-water, y+water, visited, q)
#x->z
if x>0 and z<c:
water = min(x, c-z)
pour(x-water, y, visited, q)
#y->x
if y>0 and x<a:
water = min(a-x, y)
pour(x+water, y-water, visited, q)
#y->z
if y>0 and z<c:
water = min(y, c-z)
pour(x, y-water, visited, q)
#z->x
if z>0 and x<a:
water = min(z, a-x)
pour(x+water, y, visited, q)
#z->y
if z>0 and y<b:
water = min(z, b-y)
pour(x, y+water, visited, q)
return ans
a, b, c = map(int, input().split())
visited = [[0]*(b+1) for _ in range(a+1)]
result = bfs(a, b, c, visited)
result.sort()
print(*result)
