🍶 물통

02 Aug 2022 in Algorithm on Graph search

백준 Gold5

물통

문제

---

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

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

입력

---

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

출력

---

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

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

📖 가져다 쓰기

결론적으로 말하면 [그래프 탐색]을 사용하여 풀어야 한다. 모든 그래프를 탐색해야 하므로 BFS,DFS 무엇을 사용하든 상관 없다.

나는 아직까지도 이 문제가 왜 그래프 탐색 문제인지 이해가 가지 않는다. 논리 진행 과정은 솔루션을 통하여 이해를 하였지만 어떻게 하면 이 문제를 보고 그래프 탐색이라는 알고리즘을 떠올릴 수 있을까? 센스인건가.. 😭

이 질문은 스터디 멤버들과 같이 토론을 해보아야겠다.

📐 과정 설계/관리 🔗

명쾌하고 깔끔하게 푼 사람이 있어서 내용을 가져와 보았다.

CODE

from collections import deque
import sys
input = sys.stdin.readline

def pour(x,y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x,y))

def bfs():
    while q:
        x,y = q.popleft()
        z = c-x-y

        if x == 0:
            result.append(z)

        # A --> B
        water = min(x,b-y)
        pour(x-water,y+water)

        # A --> C
        water = min(x,c-z)
        pour(x-water,y)

        # B --> A
        water = min(y,a-x)
        pour(x+water,y-water)

        # B --> C
        water = min(y,c-z)
        pour(x,y-water)

        # C --> A
        water = min(z,a-x)
        pour(x+water,y)

        # C --> B
        water = min(z,b-y)
        pour(x,y+water)

a,b,c = map(int,input().split())
visited = [[False]*(b+1) for _ in range(a+1)]
visited[0][0] = True
q = deque([(0,0)])
result = []

bfs()
result.sort()
print(*result)