[백준] 2251번: 물통 / Python / 너비우선탐색(BFS)

물통

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

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

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

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

풀이

• A, B, C 3개의 물통에서 물을 한 번 옮겨담는 경우의 수는 6가지가 있다.
• BFS로 완전탐색을 구현하면 된다.
• 물의 총량은 C물통의 용량으로 정해져 있으므로 A물통에 담긴 물을 x, B물통에 담긴 물을 y, C물통에 담긴 물을 z라고 하면 z = c - x - y가 성립한다. 따라서 x, y 두 변수만으로도 경우의 수를 표현할 수 있다.
• 방문 여부를 저장하는 visited 배열을 (A+1) x (B+1) 크기의 2차원 배열로 만들어서 경우의 수를 체크하자.

from collections import deque

a, b, c = map(int, input().split())

# 경우의 수를 담을 큐
q = deque()
q.append((0, 0))

# 방문 여부 저장
visited = [[False] * (b + 1) for _ in range(a + 1)]
visited[0][0] = True

answer = []

def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))
        
def bfs():
    while q:
        # A물통에 있는 물: x, B물통에 있는 물: y, C물통에 있는 물: z
        x, y = q.popleft()
        z = c - x - y
        
        # A 물통이 비어있는 경우에 C 물통에 남아있는 양 저장
        if x == 0:
            answer.append(z)
            
        # A에서 B로 물 이동
        water = min(x, b - y)
        pour(x - water, y + water)
        # A에서 C로 물 이동
        water = min(x, c - z)
        pour(x - water, y)
        
        # B에서 C로 물 이동
        water = min(y, c - z)
        pour(x, y - water)
        # B에서 A로 물 이동
        water = min(y, a - x)
        pour(x + water, y - water)
        
        # C에서 A로 물 이동
        water = min(z, a - x)
        pour(x + water, y)
        # C에서 B로 물 이동
        water = min(z, b - y)
        pour(x, y + water)
        
bfs()

answer.sort()
for i in answer:
    print(i, end=" ")