🍶 물통
문제
각각 부피가 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)
0x68656C6C6F21