[백준] 2251번 물통 - Python / 알고리즘 중급 2/3 - BFS (연습 2)

ByungJik_Oh·2025년 9월 25일

[Baekjoon Online Judge]

목록 보기

237/244

💡 문제

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

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

입력

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

출력

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

💭 접근

이 문제는 A, B, C 물통의 정보가 주어졌을때 각 물통이 가질 수 있는 물의 모든 경우를 구한 뒤,
A 물통이 비어있을때 C 물통이 가질 수 있는 물의 양의 모든 경우의 수를 출력하는 문제이다.

따라서 A, B, C 물통의 모든 가능한 경우의 수를 구하기 위해 BFS를 사용할 수 있다.

BFS를 돌 때, 다른 물통에 물을 나눠줄 물통과 이 물을 받을 물통을 고른다.

for i in range(3):
    if curr[i] == 0:
        continue
    for j in range(3):
        next = curr[:]
        if i == j or next[j] == v[j]:
            continue

이때 만약 두 물통을 같은 물통을 선택한 경우와 물을 받을 물통(next[j])가 이미 최대로 물이 담겨져 있을 때는 건너뛴다.

이후 다음 조건에 따라 물을 옮기면 되는데, 물을 나눠줄 물통의 물과 물을 받을 물통의 합이 물을 받을 물통의 최대치보다 작다면 나눠줄 물통을 0으로 하고 받을 물통은 단순히 더한다.

if next[i] + next[j] <= v[j]:
    next[j] += next[i]
    next[i] = 0

반면에, 최대치를 넘어 물을 모두 나눠줄 수 없는 경우는 다음과 같이 계산한다.

elif next[i] + next[j] > v[j]:
    next[i] -= (v[j] - next[j])
    next[j] = v[j]

이후, 물을 옮기는 작업이 끝났다면 이미 세 물통의 상태가 처음이라면 큐에 append해준다.

if tuple(next) not in visited:
    q.append(next)
    visited.add(tuple(next))

이렇게 BFS 함수가 종료되면 A 물통이 비어있는 경우 C 물통에 존재할 수 있는 물양의 경우를 구하면 된다.

ans = set()
for a, b, c in visited:
    if a == 0:
        ans.add(c)
print(*sorted(list(ans)))

📒 코드

from collections import deque

def bfs(start):
    q = deque()
    q.append(start)
    
    visited.add(start)

    while q:
        curr = list(q.popleft())

        for i in range(3):
            if curr[i] == 0:
                continue

            for j in range(3):
                if i == j or curr[j] == max_v[j]:
                    continue
                    
                next = curr[:]
                if next[i] + next[j] > max_v[j]:
                    next[i] = curr[i] - (max_v[j] - curr[j])
                    next[j] = max_v[j]
                elif next[i] + next[j] <= max_v[j]:
                    next[i] = 0
                    next[j] = curr[i] + curr[j]
                    
                if (next[0], next[1], next[2]) not in visited:
                    visited.add((next[0], next[1], next[2]))
                    q.append(next)

max_v = list(map(int, input().split()))

visited = set()
bfs((0, 0, max_v[2]))

ans = set()
for aw, bw, cw in visited:
    if aw == 0:
        ans.add(cw)

print(*sorted(ans))