[백준 2251 : PYTHON] 물통

문제 풀기 : 2251번

2251번: 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다.

처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다.

어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 때, 한 물통이 비거나 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다.

첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구한다.

문제풀이

모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다.

물통에 들어있을 수 있는 모든 경우의 수를 찾아서 첫번째 물통이 비어있을 때 세번째 물통의 양을 구한다.

물통에 들어있는 물 양의 경우의 수를 구하는 방법은

1. 물을 옮기는 방법의 수를 찾는다.

   x -> y, x -> z, y -> x, y -> z, z -> x, z -> y : 6가지

   예) x -> y

   

   water = min(x, b - y) : x에서 y로 옮길 물. x 전체를 옮기거나 b물통을 꽉 채우는 방법이 있다.

   pour(x - water, y + water) : 옮긴 후의 x와 y의 상태를 큐에 저장한다.

2. c물통에 남아있는 물의 양은

   z = c- x- y

3. visited로 (x, y)경우의 수에 대한 중복을 방지한다.

전체코드

import sys
from collections import deque

# x, y의 경우의 수 저장
def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))

def bfs():

    while q:
        # x : a물통의 물의 양, y : b물통의 물의 양, z : c물통의 물의 양
        x, y = q.popleft()
        z = c - x - y

        # a 물통이 비어있는 경우 c 물통에 남아있는 양 저장
        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())

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

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

# 답을 저장할 배열
answer = []

bfs()

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