백준 2251번: 물통

BOJ

백준 2251번: 물통

접근

모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다.

“처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다.”

• 편의상 물통을 각각 x, y, z 라 하자.
• z 물통의 양은 z = C - x - y로 구할 수 있다.
• bfs(x, y)로 풀 수 있다.

“첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.”

• x 물통 속에 있는 물의 양이 0이 되면, z 물통 속에 있는 물의 양을 저장
• if x == 0: ans.append(z)

물을 옮길 수 있는 방법(6가지) A -> B, A -> C, B -> A, B -> C, C -> A, C -> B

# A -> B 로 물을 옮길 때
water = min(x, B - y)
pour(x - water, y + water)

Correct Solution

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

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

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


def bfs():
    # bfs 시작!
    q.append([0, 0])
    visit[0][0] = True

    while q:
        x, y = q.popleft()
        z = C - x - y
        if x == 0:
            ans.append(z)

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

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

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

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

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

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


q = deque()
ans = []

visit = [[False] * (B + 1) for _ in range(A + 1)]
bfs()

ans.sort()
print(' '.join(map(str, ans)))

참고 사이트

오뚝이개발자