[Python] 백준 2251번 - 물통 (골드 5)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - DFS
 - BFS

 

https://www.acmicpc.net/problem/2251

2251번: 물통

 

문제

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

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

입력

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

출력

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

 

 

---

 

이 문제를 DFS를 이용해 풀어야겠다 라는 가닥은 잡았으나

 

parameter값을 어떻게 넘겨서 dfs를 완성하지? 라는 고민을 끝내 해결하지 못하였다.

 

검색해보니 해결법은 간단했으나 난 이 방법을 떠올리기 쉽지 않았을것 같다.

 

 

각 물통을 식으로 나타내면 위와 같으며 각 물통이 조금이라도 채워져 있을 때 다른 두 물통으로 보내는 모든 경우의 수를 DFS를 통해 확인하는 것이다.

 

import sys
input = sys.stdin.readline

A, B, C = map(int, input().split())

CSet = set()
visited = set()
def dfs(a, b, c):
    if a == 0:
        CSet.add(c)
    if (a, b, c) not in visited:
        visited.add((a, b, c))
        if a != 0:
            if B - b <= a:
                dfs(a-B+b, B, c)
            else:
                dfs(0, a+b, c)
            if C - c <= a:
                dfs(a-C+c, b, C)
            else:
                dfs(0, b, a+c)
        if b != 0:
            if A-a <= b:
                dfs(A, b-A+a, c)
            else:
                dfs(a+b, 0, c)
            if C-c <= b:
                dfs(a, b-C+c, C)
            else:
                dfs(a, 0, b+c)
        if c != 0:
            if A-a <= c:
                dfs(A, b, c-A+a)
            else:
                dfs(a+c, b, 0)
            if B-b <= c:
                dfs(a, B, c-B+b)
            else:
                dfs(a, b+c, 0)
        
    pass

dfs(0, 0, C)
cList = list(CSet)
cList.sort()
for i in cList:
    print(i, end=' ')