[백준] 2251번: 물통

문제

https://www.acmicpc.net/problem/2251

2251번: 물통

 

풀이

BFS(너비 우선 탐색)를 사용해 풀었습니다.

총 6가지의 가능한 경우의 수를 모두 확인합니다.

check 배열은 중복을 방지하기 위해 A 물통과 B 물통에 담겨 있는 물양을 체크합니다.

C 물통에 담겨 있는 물의 양은 C 물통의 부피 - (A 물통의 물양 + B 물통의 물양)이 됩니다.

 

코드

파이썬

from collections import deque
import sys

input = sys.stdin.readline


def BFS():
    answer = []

    def pour(a, b):
        if not check[a][b]:
            check[a][b] = True
            queue.append((a, b))

    queue = deque()
    check = [[False] * (B + 1) for _ in range(A + 1)]
    check[0][0] = True
    queue.append((0, 0))
    while queue:
        a, b = queue.popleft()
        c = C - (a + b)

        if a == 0:
            answer.append(c)

        # A -> B
        water = min(a, B - b)
        pour(a - water, b + water)
        # A -> C
        water = min(a, C - c)
        pour(a - water, b)
        # B -> A
        water = min(b, A - a)
        pour(a + water, b - water)
        # B -> C
        water = min(b, C - c)
        pour(a, b - water)
        # C -> A
        water = min(c, A - a)
        pour(a + water, b)
        # C -> B
        water = min(c, B - b)
        pour(a, b + water)

    return sorted(answer)


A, B, C = map(int, input().split())
for x in BFS():
    print(x, end=" ")