[BOJ] 2251번 물통 파이썬

문제

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

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

입력

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

출력

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

풀이

#bfs

1. 방문 기준 : a 물통에 들어있는 물 양, b 물통에 들어있는 물 양

2. 물을 옮길 수 있는 모든 경우의 수에 대해 옮긴 후의 a,b의 물 양을 큐에 저장한다.

 - x → y / x → z / y → x / y → z / z → x / z → y 의 경우의 수 존재

 - 옮기게 되는 물 양은 출발지에 담긴 물 양과 도착지에 남은 공간 중 최솟값에 해당한다. (물을 다 채우거나 다 비우는 방식으로만 옮길 수 있기 때문)

3. x == 0, 즉 a 물통이 빈 통이 됐을 때 answer 배열에 z를 저장한다.

 

코드

import sys

def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))

def bfs():
    while q:
        x, y = q.pop()
        z = c-x-y

        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())
visited = [[False] * (b+1) for _ in range(a+1)]
answer = []
q = [(0,0)]
visited[0][0]=True
bfs()

answer.sort()
print(*answer)