백준알고리즘 - 2251번 물통 - 파이썬(Python)

문제

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

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

 

입력

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

 

출력

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

 

예제 입력과 출력

 

 

알고리즘 분류

BFS

 

정답

 

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

def cou(s1,s2):
    if ch[s1][s2] != 1:
        ch[s1][s2] = 1
        de.append([s1,s2])

def bfs():
    de.append([0,0])
    ch[0][0]=1

    while de:
        a1,b1=de.popleft()
        c1 =c-a1-b1
        
        if a1 == 0:
            r.append(c1)

        if b1+a1 < b: # a를 b로
            cou(0, b1+a1)
        else:
            cou(a1-(b-b1), b)

        if c1+a1 < c: # a를 c로
            cou(0, b1)
        else:
            cou(a1-(c-c1), b1)

        if a1+b1 < a: # b를 a로
            cou(a1+b1, 0)
        else:
            cou(a, b1-(a-a1))

        if c1+b1 < c: # b를 c로
            cou(a1, 0)
        else:
            cou(a1, b1-(c-c1))

        if a1+c1 < a: # c를 a로
            cou(a1+c1,b1)
        else:
            cou(a, b1)

        if b1+c1 < b: # c를 b로
            cou(a1, c1+b1)
        else:
            cou(a1, b)

a,b,c=map(int,input().split())
ch=[[0]*201 for i in range(201)]
r=[]
de=deque()

bfs()
r.sort()

print(' '.join(map(str,r)))

처음 c에만 물이 있고 a와 b에는 물이 없기 때문에 (0, 0)에서 bfs를 시작합니다.
큐에 넣거나 체크를 할 때 a와 b의 값으로 비교를 합니다.
c의 값은 c에서 a와 b에 있는 물의 값을 빼는 것을 통해 구할 수 있기 때문에 따로 배열에 넣지 않았습니다.

 

물을 옮길 수 있는 방법은 6가지입니다.
a→b, a→c, b→a, b→c, c→a, c→b

 

각각의 경우에 물을 옮길 수 있다면 중복체크를 하고 옮기고 첫 번째 물통 a가 비어있으면 리스트 r에 c에 있는 물의 양을 저장합니다.

bfs 완료 후 리스트 r에 있는 값들을 오름차순으로 정렬해서 출력합니다.

 

---

백준 알고리즘 2251번 : https://www.acmicpc.net/problem/2251

2251번: 물통