[solved.ac 실버1] 2251_물통 (BFS 풀이)

문제

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

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

입력

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

출력

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

예제

 

---

나의 풀이

이 문제를 보고 DFS/BFS 풀이를 떠올릴 수 있었냐가 관건인 문제였다.

얼핏 봐서는 쉽게 DFS/BFS를 떠올리기 힘들다.

이 문제가 DFS/BFS 문제인 이유는 다음과 같다.

 

현재 물통이 3개가 있고, 문제에서 보면 물통의 용량을 입력 받는다. 이 용량을 A, B, C 라고 하겠다.

그리고 실제 물의 양은 A에는 a만큼, B에는 b만큼, C에는 c만큼 들어있다고 정의하겠다.

문제에 따르면 가장 처음에는 세 번째 물통에만 물이 차있다고 했기 때문에 (a, b, c) = (0, 0, C)  가 될 것이다.

 

예를 들어 물통의 용량이 10, 6, 15 라고 했을 때, 초기에는 (0, 0, 15) 만큼의 물이 저장되어 있을 것이고, 이 물을 첫 번째, 두 번째 물통에 옮기는 경우를 생각해보면 첫 번째 물통에 옮겼을 때는 (10, 0, 5) 가 되고, 두 번째 물통에 옮겼을 때는 (0, 6, 9)가 된다.

 

물을 옮기는 경우는 6가지가 있다. (편의상 물통 A, B, C 라고 하겠다)

1. A -> B
2. A -> C
3. B -> A
4. B -> C
5. C -> A
6. C -> B

이렇게 물을 옮기는 부분을 함수로 분리하여 다음과 같이 작성했다.

def move(state):
    a, b, c = state
    answer = set()
    # A -> B
    amount = min(a, B-b)
    answer.add((a-amount, b+amount, c))
    # A -> C
    amount = min(a, C-c)
    answer.add((a-amount, b, c+amount))
    # B -> A
    amount = min(b, A-a)
    answer.add((a+amount, b-amount, c))
    # B -> C
    amount = min(b, C-c)
    answer.add((a, b-amount, c+amount))
    # C -> A
    amount = min(c, A-a)
    answer.add((a+amount, b, c-amount))
    # C -> B
    amount = min(c, B-b)
    answer.add((a, b+amount, c-amount))
    return sorted(answer)

매개 변수인 state는 현재 물의 양인 (a, b, c)를 의미한다.

예를 들어 A -> B로 물을 옮긴다고 했을 때, a의 양(A 물통의 물)과 B-b(B 물통에 더 채울 수 있는 용량) 중 더 작은 값 만큼 옮길 수 있다.

이 과정을 위에서 정리한 6가지 경우에 대해 수행하며 answer이라는 set에 집어 넣는다. (물을 옮길 수 없는 경우 같은 값이 중복으로 나올 수 있기 때문에 중복을 제거하기 위한 선택이다.)

그리고 정렬하여 리스트 형태로 반환했다.

 

이 문제는 DFS나 BFS 중 아무거나 선택해서 풀 수 있지만 나는 BFS 풀이를 사용하여 풀이했다.

graph 변수는 어떤 상태 (a, b, c) 에서 물을 옮겨서 나올 수 있는 경우의 수를 저장한 dict 자료형을 사용했다. 이때 key는 상태(a, b, c)가 되고, value는 모든 경우의 수가 저장된 리스트이다.

일반적인 BFS에서는 visited라는 리스트를 사용해 방문을 탐색하지만 이 문제에서 graph는 dict 자료형을 사용했기 때문에 방문한 노드는 graph의 키로 저장이 된다.

그렇기 때문에 방문 확인은 graph.keys()에 해당 노드가 있는지 확인하면 된다.

from collections import deque

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

def move(state):
    a, b, c = state
    answer = set()
    # A -> B
    amount = min(a, B-b)
    answer.add((a-amount, b+amount, c))
    # A -> C
    amount = min(a, C-c)
    answer.add((a-amount, b, c+amount))
    # B -> A
    amount = min(b, A-a)
    answer.add((a+amount, b-amount, c))
    # B -> C
    amount = min(b, C-c)
    answer.add((a, b-amount, c+amount))
    # C -> A
    amount = min(c, A-a)
    answer.add((a+amount, b, c-amount))
    # C -> B
    amount = min(c, B-b)
    answer.add((a, b+amount, c-amount))
    return sorted(answer)

graph = {(A,B,C):move((0, 0, C))}

queue = deque([(0, 0, C)])
while queue:
    x = queue.popleft()
    if x not in graph.keys():
        graph[x] = move(x)
        for state in move(x):
            queue.append(state)
for k in sorted(graph.keys(), key=lambda x: x[2]):
    if k[0] == 0: print(k[2], end=' ')

채점 결과