문제

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

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

# 2251
import sys
input = lambda: sys.stdin.readline().strip()

# 1. 다른 물통에 물을 붓는다.
# 2. 첫 번째 물통이 비어있는 경우, 세 번째 물통의 물의 양을 구한다.
# 3. 세 물통의 구성이 이전에 구성되었다면 물을 옮기지 않는다.

from collections import deque
max_A, max_B, max_C = map(int, input().split())
check = []
for i in range(201):
    check.append([])
    for j in range(201):
        check[i].append([False] * 201)

def water(num1, num2, num3, max2, max3):
    arr = []
    if num1 + num2 > max2:
        num1, num2 = num1 - (max2 - num2), max2
    else:
        num1, num2 = 0, num1 + num2
    arr.append([num1, num2, num3])
        
    if num1 + num3 > max3:
        num1, num3 = num1 - (max3 - num3), max3
    else:
        num1, num3 = 0, num1 + num3
    arr.append([num1, num2, num3])
    
    return arr


def bfs():
    global max_A, max_B, max_C, check
    output = []
    
    queue = deque()
    queue.append((0, 0, max_C))
    check[0][0][max_C] = True
    while queue:
        A, B, C = queue.popleft()
        if (C not in output) and A == 0:
            output.append(C)
        
        # 1. 첫 번째 물통을 붓는다
        # 1-1. 두 번째 물통부터 물을 받는다
        numbers = water(A, B, C, max_B, max_C)
        for number in numbers:
            a, b, c = number[0], number[1], number[2]

            if check[a][b][c] == False:
                check[a][b][c] = True
                queue.append((a, b, c))
            
        # 1-2. 세 번째 물통부터 물을 받는다
        numbers = water(A, C, B, max_C, max_B)
        for number in numbers:
            a, b, c = number[0], number[2], number[1]

            if check[a][b][c] == False:
                check[a][b][c] = True
                queue.append((a, b, c))
        
        # 2. 두 번째 물통을 붓는다
        # 2-1. 첫 번째 물통부터 물을 받는다
        numbers = water(B, A, C, max_A, max_C)
        for number in numbers:
            a, b, c = number[1], number[0], number[2]

            if check[a][b][c] == False:
                check[a][b][c] = True
                queue.append((a, b, c))

        # 2-2. 세 번째 물통부터 물을 받는다
        numbers = water(B, C, A, max_C, max_A)
        for number in numbers:
            a, b, c = number[2], number[0], number[1]

            if check[a][b][c] == False:
                check[a][b][c] = True
                queue.append((a, b, c))
        
        # 3. 세 번째 물통을 붓는다
        # 3-1. 첫 번째 물통부터 물을 받는다
        numbers = water(C, A, B, max_A, max_B)
        for number in numbers:
            a, b, c = number[1], number[2], number[0]

            if check[a][b][c] == False:
                check[a][b][c] = True
                queue.append((a, b, c))
                
        # 3-2. 두 번째 물통부터 물을 받는다
        numbers = water(C, B, A, max_B, max_A)
        for number in numbers:
            a, b, c = number[2], number[1], number[0]

            if check[a][b][c] == False:
                check[a][b][c] = True
                queue.append((a, b, c))
                
    output.sort()
    return output
    
print(*bfs())

백준 2251 물통