📚 2251 - 물통

물통

이해

만약, 이 문제가 어떻게 되었는지 이해가 되지 않는다면
이 예시를 보기를 바란다! (나또한 처음 문제를 볼 때 이해가 안되서 자료를 찾게 되었다.)

세 개의 물통 부피 : 8 9 10
첫 시작시 : 0 0 10 o
8 0 2 a에 가득
8 2 0 남은거 c로
0 2 8 o a전체 c로
0 9 1 o c에서 b로 남은거 채우기
0 8 2 o
8 1 1
0 1 9 o

➡️ 1 2 8 9 10

위를 보고 아~ 그렇구나 생각이 들면 다시 문제 풀러 고고

이제 문제를 어떻게 풀면 되는지 적어보려고 한다.
brute_force 알고리즘의 특징으로 경우의 수를 구해야 한다.
현재 물통간의 물을 이동할 수 있는 경우의 수는 이와 같다.

a → b
a → c
b → a
b → c
c → a
c → b

그리고, a + b + c = 총 크기 이니, c = 총 크기 - a - b인 공식이 성립한다.

소스

from collections import deque
import sys

read = sys.stdin.readline

aBucket, bBucket, cBucket = map(int, read().split())


def bfs():
    q = deque()
    q.append((0, 0))
    visited = [[0] * 210 for _ in range(210)]
    result = []

    while q:
        a, b = q.popleft()
        c = cBucket - a - b
        if visited[a][b]:
            continue
        visited[a][b] = 1
        if a == 0:
            result.append(c)

        # 1 ~ 6가지
        # (1) a->b
        water = min(a, bBucket - b)
        q.append((a - water, b + water))
        # (2) a->c
        water = min(a, cBucket - c)
        q.append((a - water, b))
        # (3) b->a
        water = min(b, aBucket - a)
        q.append((a + water, b - water))
        # (4) b->c
        water = min(b, cBucket - c)
        q.append((a, b - water))
        # (5) c->a
        water = min(c, aBucket - a)
        q.append((a + water, b))
        # (6) c->b
        water = min(c, bBucket - b)
        q.append((a, b + water))

    return sorted(result)


print(' '.join(map(str, bfs())))

채점 결과