[Algorithm] BaekJoon : 2251. 물통 by Python

[문제 바로가기] https://www.acmicpc.net/problem/2251

📌문제 설명

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

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

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

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

---

💡 문제 풀이

BFS 알고리즘을 활용하여 해결한 문제!

3개의 물통이 있을 때 하나의 물통에서 다른 물통으로 옮길 수 있는 모든 경우를 확인하면 된다. - 이중반복문 사용

1. 반복문을 사용하여 3개의 물통에 대해 옮길 수 있는 물이 있는지 확인 (물의 양이 0 이상인 경우)

2. 1번에서 선택한 물통을 제외한 다른 물통(물통의 번호(인덱스)가 같으면 continue)으로 물의 양을 옮긴다.
   2.1 물의 양을 옮길 때 넘치는 경우(물 용량 초과)와 그렇지 않은 경우를 확인하여 각 상황에 맞게 계산한다.

3. 1~2번으로 만든 경우가 이전에 나온적이 없다면 visited, queue에 담는다.

4. BFS 완료 후 원하는 결과를 answer 배열에 담고 정렬한 후 출력한다.

※ 문제에서 요구하는 것은 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양이다

첫 번째 물통이 비어있는 조건을 놓쳐서 예제를 이해하는데 헤맸다...😂

코드는 다음과 같다.

import sys
from collections import deque

value = list(map(int, input().split()))
visited = [[0, 0, value[2]]]
queue = deque([[0, 0, value[2]]])
while queue:
    arr = queue.popleft()
    for i in range(3):
        if arr[i]:
            for j in range(3):
                if i == j: continue
                temp = arr[::]
                test = temp[i] + temp[j] # 물을 옮기게 되었을 때
                if test > value[j]: # 넘치는 경우
                    temp[i] = test - value[j]
                    temp[j] = value[j]
                else: 		    # 넘치지 않는 경우
                    temp[j] += temp[i]
                    temp[i] = 0
                if temp not in visited:
                    visited.append(temp)
                    queue.append(temp)

answer = []
for a, b, c in visited:
    if a == 0 and c not in answer:
        answer.append(c)
answer.sort()
print(' '.join(map(str, answer)))

---