[BOJ] 2251 물통

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

2251번: 물통

문제

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

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

입력

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

출력

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

풀이

최근에 계속해서 그래프 이론 문제들을 풀고 있다. 위 문제 또한 DFS아니면 BFS를 이용해서 풀 수 있는데, 나는 BFS맨이므로 BFS를 사용했다(Deque이 최고야). 역시 이 문제는 조건들을 하드코딩하느라 힘들었다. 정말 세세한 부분까지 코드를 설정했기에, 말로 설명하기에는 무리가 있다고 본다. 대강 얘기하자면 각 물통이 비어있지 않을때 다른 두 개의 물통에 물을 넣을 경우를 다른 물통이 얼마나 차있는지에 따라 비교하며 넣었다. 구현이 어렵지 생각해내는 것은 그렇게 어렵지 않은 문제였다.

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
A, B, C = map(int, input().split())
ans = [False for _ in range(C+1)]
q = deque()
q.append([0, 0, C])
visited = []
while q:
    a, b, c = q.popleft()
    #print(a, b, c)
    if [a, b, c] not in visited:
        visited.append([a, b, c])
        if a == 0:
            ans[c] = True
    else:
        continue
    if a != 0:
        if b < B:
            if B-b > a:
                q.append([0, b+a, c])
            else:
                q.append([a-(B-b), B, c])
        if c < C:
            if C-c > a:
                q.append([0, b, c+a])
            else:
                q.append([a-(C-c), b, C])
    if b != 0:
        if a < A:
            if A-a > b:
                q.append([a+b, 0, c])
            else:
                q.append([A, b-(A-a), c])
        if c < C:
            if C-c > b:
                q.append([a, 0, c+b])
            else:
                q.append([a, b-(C-c), C])
    if c != 0:
        if a < A:
            if A-a > c:
                q.append([a+c, b, 0])
            else:
                q.append([A, b, c-(A-a)])
        if b < B:
            if B-b > c:
                q.append([a, b+c, 0])
            else:
                q.append([a, B, c-(B-b)])

for i in range(C+1):
    if ans[i]:
        print(i, end = ' ')