[백준/Python(파이썬)] 2251 물통

문제

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

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

입력

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

출력

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

풀이

a, b, c 세 가지 물병으로 주고 받을 수 있는 경우의 수를 BFS 안에서 조건문을 통해 구현한다.

BFS에서 사용하는 큐와 방문 여부를 체크하는 visited 배열에 들어가는 값을 a, b 물통의 현재 담긴 물의 양으로 한다.

현재 c값은 c에서 배열에 들어간 a, b 물통의 현재 물의 양을 통해 구한다.

소스코드

from collections import deque

def isVisited(a1, b1):
    if visited[a1][b1] == 0:
        visited[a1][b1] = 1
        q.append([a1, b1])

def bfs():
    while q:
        a1, b1 = q.popleft()
        c1 = c - a1 - b1
        if a1 == 0:
            ans.append(c1)

        if a1 + b1 < b:  # a->b
            isVisited(0, a1 + b1)
        else:
            isVisited(a1-(b-b1), b)

        if a1 + c1 < c:  # a->c
            isVisited(0, b1)
        else:
            isVisited(a1 - (c - c1), b1)

        if a1 + b1 < a:  # b->a
            isVisited(a1 + b1, 0)
        else:
            isVisited(a, b1 - (a - a1))

        if c1 + b1 < c:  # b->c
            isVisited(a1, 0)
        else:
            isVisited(a1, b1 - (c - c1))

        if a1 + c1 < a:  # c->a
            isVisited(a1 + c1, b1)
        else:
            isVisited(a, b1)

        if c1 + b1 < b:  # c->b
            isVisited(a1, b1 + c1)
        else:
            isVisited(a1, b)

a,b,c = map(int, input().split())
MAX = 201
visited = [[0]* MAX for _ in range(MAX)]
visited[0][0] = 1

q = deque()
q.append([0, 0])  # 첫 번째, 두 번째 물병의 남은 용량을 표시

ans = []
bfs()
ans.sort()
print(' '.join(map(str, ans)))

Git : github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_2251.py

문제 : www.acmicpc.net/problem/2251