BOJ 2251 물통

https://www.acmicpc.net/problem/2251
시간 2초, 메모리 128MB
input :

• A, B, C(1≤A, B, C≤200)

output :

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

조건 :

• 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다.
• 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다.
• 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는

---

맨 처음에 이건 뭔가 쉬운 풀이 방법이 있겠다 싶어 한 40분 삽질을 했지만, 응 BFS 써야 해.... 매우 많은 경우가 존재하기 때문에 특정한 무언가를 만들 수 없었다.

3개의 물통을 가지고 있는데.
우리가 x, y 안의 물량을 알고 있으면 z 의 물을 구할 수 있기 때문에 visit리스트는
x, y 에 대해서 가지게 한다.

그렇다면 경우의 수는 몇 가지 인가?
x -> y, z
y -> x, z
z -> x, y

총 6가지이다.

물을 전해줄 때.
만약 x -> y라고 하자.
x + y 가 b 양 보다 크다면
(x + y - b, b, z) 로 채울 수 있지만,
작다면 (0, x + y, z) 로 채워야 한다.

두 값을 더해줘서 내가 옮기려고 하는 물통의 총량 만큼 채우고 나머지는 원래 있던 곳에 둔다.
이를 계속 반복하자.

import sys
from _collections import deque

a, b, c = map(int, sys.stdin.readline().split())
visit = [[0] * 201 for i in range(201)]
res = set()

q = deque([])
q.append((0, 0, c))

while q:
    x, y, z = q.popleft()

    if visit[x][y] == 1:
        continue

    visit[x][y] = 1

    if x == 0:
        res.add(z)

    if x + y > b:
        q.append((x + y - b, b, z))
    else:
        q.append((0, x + y, z))

    if x + z > c:
        q.append((x + z - c, y, c))
    else:
        q.append((0, y, x + z))

    if y + x > a:
        q.append((a, y + x - a, z))
    else:
        q.append((y + x, 0, z))

    if y + z > c:
        q.append((x, y + z - c, c))
    else:
        q.append((x, 0, y + z))

    if z + x > a:
        q.append((a, y, z + x - a))
    else:
        q.append((z + x, y, 0))

    if z + y > b:
        q.append((x, b, z + y - b))
    else:
        q.append((x, z + y, 0))

res = sorted(res)
for item in res:
    print(item, end=" ")