[Algorithm🧬] 백준 14687 : 물통

문제

처음 접근을 완전 헛다리 짚은 문제...
DP 라고 생각했는데, a, b 의 범위가 너무 커서 아닐 것 같긴 했으나 다른 방법이 안떠올라서 고민하다가 찾아봤는데 BFS 로 푸는 거였다...

근데 계속 50%? 쯤에서 틀려서 대체 뭔가 했더니,
목표가 0 0 이면 바로 0 으로 걸러줘야되는데 그걸 거르는게 없어서 틀린거였음.

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

# a -> b
def Move(ca, cb, a, b):
    nb = (b + a) if a <= (cb - b) else cb
    na = a - (nb - b)

    return (na, nb)


def BFS():
    visited = set((0, 0))
    q = deque()
    q.append((0, 0, 0))

    # 이거 처음에 안걸러서 틀린거였음!!!
    if ea == 0 and eb == 0:
        return 0
    

    # Fill / Empty / Move
    # 1 은 Fill -1 은 Empty 
    # -2 2 는 주고 받기.
    
    while q:
        a, b, cnt = q.popleft()

        x, y = Move(cb, ca, b, a)
        move = [(ca, b), (a, cb), (0, b), (a, 0), Move(ca, cb, a, b), (y, x)]

        for na, nb in move:
            if (na, nb) == (ea, eb):
                return cnt + 1

            if (na, nb) in visited:
                continue

            visited.add((na, nb))
            q.append((na, nb, cnt + 1))

    return -1


ca, cb, ea, eb = map(int, readl().split())

print(BFS())