2251 - 물통
문제
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
코드
from collections import deque
A, B, C = map(int, input().split())
visited = [[False] * 201 for _ in range(201)]
def calc(a, b):
global q
if not visited[a][b]:
visited[a][b] = True
q.append((a, b))
result = []
q = deque()
q.append((0, 0))
visited[0][0] = True
while q:
x, y = q.popleft()
z = C - x - y
if x == 0:
result.append(z)
# A -> B
if x > 0 and y < B:
val = min(x, B-y)
calc(x-val, y+val)
# B -> A
if y > 0 and x < A:
val = min(y, A-x)
calc(x+val, y-val)
# B -> C
if y > 0 and z < C:
val = min(y, C-z)
calc(x, y-val)
# C -> B
if z > 0 and y < B:
val = min(z, B-y)
calc(x, y+val)
# A -> C
if x > 0 and z < C:
val = min(x, C-z)
calc(x-val, y)
# C -> A
if z > 0 and x < A:
val = min(z, A-x)
calc(x+val, y)
result.sort()
print(*result)한마디
물통이 A, B, C 3개이기 때문에 물을 옮길 수 있는 경우는 총 6가지이다.
a -> b / a -> c / b -> c / b -> a / c -> a / c -> b따라서 BFS를 이용해 각 경우를 탐색하면서 A 물통이 빈 경우만을 result 배열에 담아줬다.
