[BOJ] 14867번: 물통

14867번: 물통

다른 친구가 우선 순위 큐를 이용해서 풀었다고 하고, 인터넷에 풀이 올리신 걸 보니 BFS or DFS로 푸시는 걸 보고 감이 안 잡혔다. ㅠㅠ

아무튼 나는 1. A에서만 물통을 채워서 B에게 넘겨주는 작업, 2. B에서만 물통을 채워서 A에게 넘겨주는 작업. 이 둘 중에서 최소 작업 횟수를 출력하게 만들었다. 사실 코드가 굉장히 미개하다. 왜냐하면 중복이 너무 많기 때문이다...

 코드를 짤 때 생각해야 할 점이 -1을 출력할 때인데 bucketA == a && bucketB == b일 때가 못 만들 때이다. 왜냐하면 이 때는 어짜피 bucketA, bucketB를 비워줘야 하는데 이렇게 되면 처음 시작할 때와 똑같은 상황이기 때문이다.

또한 a == c && b == d일때는 2를 출력해 줘야하고, c == 0 && d == 0일 때는 처음 작업과 같으므로 0을 출력해 줘야한다.(예외처리를 해줘야 한다는 말.)

#include <cstdio>
#define min(a, b) ((a) < (b) ? (a) : (b))
bool flag = false;
int a, b, c, d;
int bucketA = 0, bucketB = 0;
int cntfA = 0, cntfB = 0;
 
int main()
{
    scanf("%d %d %d %d", &a, &b, &c, &d);
    if (a == c && b == d)
    {
        printf("2");
        return 0;
    }
    if (c == 0 && d == 0)
    {
        printf("0");
        return 0;
    }
    while (true) {
        if (bucketA == 0) {
            bucketA = a;
            cntfA++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
        if (bucketB == b) {
            bucketB = 0;
            cntfA++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
        if (bucketB + bucketA > b) {
            bucketA = bucketA + bucketB - b;
            bucketB = b;
            cntfA++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
        else {
            bucketB += bucketA;
            bucketA = 0;
            cntfA++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
 
    }
    bucketA = 0, bucketB = 0;
    while (true) {
        if (bucketB == 0) {
            bucketB = b;
            cntfB++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
        if (bucketA == a) {
            bucketA = 0;
            cntfB++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
        if (bucketB + bucketA > a) {
            bucketB = bucketA + bucketB - a;
            bucketA = a;
            cntfB++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
        else {
            bucketA += bucketB;
            bucketB = 0;
            cntfB++;
            if (bucketA == a && bucketB == b)
                break;
            if (bucketA == c && bucketB == d) {
                flag = true;
                break;
            }
        }
    }
    cntfA = min(cntfA, cntfB);
    if (!flag) cntfA = -1;
 
    printf("%d\n", cntfA);
    return 0;
}