백준/2251/물통/Python

물통 

 

 

 

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

 

구현 

a에서 b로 이동하는 경우의 수 2가지

a -> b 에 담긴 물의 양이 b 의 전체용량보다 클 경우 , a에 있는 물의 양을 전체 다 옮기지 못하므로 부분만 이동 

그 외 경우, a에 있는 모든 물의 양을 b로 옮겨준다. 

import sys
from collections import deque

# 물을 옮기는 방법의 수
# x-> y, x-> z , y->x, y->z,z->x,z->y 6가지
# x,y 의 경우의 수 저장
def pour(x,y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))
       
def bfs():
    while q:
        # x: a 물통의 물의 양, y: b물통의 물의 양, z: c물통의 물의 양
        x,y = q.popleft()
        z = c - x - y 

        # a 물통이 비어있는 경우 c 물통에 남아있는 양 저장
        if x == 0:
            answer.append(z)

        # x-> y
        water = min(x, b - y)
        pour(x - water, y + water)
        # x-> z
        water = min(x,c-z)
        pour(x - water, y)
        # y-> x
        water = min(y, a-x)
        pour(x + water, y - water)
        # y -> z
        water = min(y, c-z)
        pour(x, y-water)
        # z -> x
        water = min(z, a-x)
        pour(x + water, y)
        # z -> y
        water = min(z, b-y)
        pour(x , y + water)


a, b, c = map(int, sys.stdin.readline().split())
 # 경우의 수를 담을 큐
q = deque()
q.append((0,0))
visited = [[False]*(b+1) for _ in range(a+1)]
visited[0][0] = True

answer = []
bfs()

answer.sort()
for i in answer:
    print(i, end=" ")