문제 개요

세 개의 컵 용량이 각각 S, N, M(S = N + M, 양의 정수)으로 주어집니다. 처음에 S 용량 컵은 가득 차 있고, 나머지는 비어 있습니다. 컵 간 콜라를 서로 붓는 작업을 최소화하여 두 컵에 S/2의 콜라가 담긴 상태를 만드는 것이 목표입니다. 단, S가 홀수이면 해결 불가능합니다.

BFS 접근 방식

각 컵의 현재 상태를 (a, b, c)로 표현하여 BFS를 적용합니다. 초기 상태는 (S, 0, 0)입니다. 한 컵에서 다른 컵으로 콜라를 부을 때 발생하는 두 가지 경우를 탐색합니다:

• 받는 컵이 가득 찰 때까지 붓기
• 주는 컵이 완전히 빌 때까지 붓기

총 6개의 방향(3P2)에 대해 각각 2가지 경우를 적용하므로 12가지 상태 전이가 발생합니다. 방문한 상태를 기록해 중복 탐색을 방지합니다.

STL 기반 구현 (tuple + map)

#include<bits/stdc++.h>
using namespace std;
const int MAX_VAL = 105;
const int INF = 0x3f3f3f3f;

int total, capA, capB;
queue<tuple<int,int,int>> stateQueue;
map<tuple<int,int,int>, int> stepCount;

bool canFill(int src, int dst, int dstCap) {
    return src >= dstCap - dst;
}

bool canEmpty(int src, int dst, int dstCap) {
    return src + dst <= dstCap;
}

void addState(tuple<int,int,int> newState) {
    if(stepCount[newState]) return;
    stepCount[newState] = stepCount[currState] + 1;
    stateQueue.push(newState);
}

void bfs() {
    tuple<int,int,int> currState = make_tuple(total, 0, 0);
    stateQueue.push(currState);
    stepCount[currState] = 0;
    int minSteps = INF;

    while(!stateQueue.empty()) {
        currState = stateQueue.front();
        stateQueue.pop();
        int a = get<0>(currState), b = get<1>(currState), c = get<2>(currState);
        
        if((a == total/2 && b == total/2) || 
           (a == total/2 && c == total/2)) {
            minSteps = stepCount[currState];
            break;
        }

        // 12가지 상태 전이 연산
        if(canFill(a, b, capA)) 
            addState(make_tuple(a - (capA - b), capA, c));
        if(canFill(a, c, capB)) 
            addState(make_tuple(a - (capB - c), b, capB));
        if(canFill(b, c, capB)) 
            addState(make_tuple(a, b - (capB - c), capB));
        if(canFill(b, a, total)) 
            addState(make_tuple(total, b - (total - a), c));
        if(canFill(c, a, total)) 
            addState(make_tuple(total, b, c - (total - a)));
        if(canFill(c, b, capA)) 
            addState(make_tuple(a, capA, c - (capA - b)));
        if(canEmpty(a, b, capA)) 
            addState(make_tuple(0, a + b, c));
        if(canEmpty(a, c, capB)) 
            addState(make_tuple(0, b, a + c));
        if(canEmpty(b, c, capB)) 
            addState(make_tuple(a, 0, b + c));
        if(canEmpty(b, a, total)) 
            addState(make_tuple(a + b, 0, c));
        if(canEmpty(c, a, total)) 
            addState(make_tuple(a + c, b, 0));
        if(canEmpty(c, b, capA)) 
            addState(make_tuple(a, b + c, 0));
    }
    cout << (minSteps == INF ? "NO" : to_string(minSteps)) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin >> total >> capA >> capB) {
        if(!total && !capA && !capB) break;
        stateQueue = queue<tuple<int,int,int>>();
        stepCount.clear();
        if(total % 2) cout << "NO\n";
        else bfs();
    }
}

구조체 + 3D 배열 구현

#include<bits/stdc++.h>
using namespace std;
const int MAX = 105;
const int INF = 0x3f3f3f3f;

int total, capA, capB;
int steps[MAX][MAX][MAX];

struct CupState { 
    int a, b, c; 
};
queue<CupState> stateQueue;

bool canFill(int src, int dst, int cap) {
    return src >= cap - dst;
}

bool canEmpty(int src, int dst, int cap) {
    return src + dst <= cap;
}

void addState(int a, int b, int c) {
    if(steps[a][b][c]) return;
    steps[a][b][c] = steps[x][y][z] + 1;
    stateQueue.push({a, b, c});
}

void bfs() {
    stateQueue.push({total, 0, 0});
    steps[total][0][0] = 0;
    int minSteps = INF;
    int x, y, z;

    while(!stateQueue.empty()) {
        CupState curr = stateQueue.front();
        stateQueue.pop();
        x = curr.a; y = curr.b; z = curr.c;

        if((x == total/2 && y == total/2) || 
           (x == total/2 && z == total/2)) {
            minSteps = steps[x][y][z];
            break;
        }

        if(canFill(x, y, capA)) addState(x - (capA - y), capA, z);
        if(canFill(x, z, capB)) addState(x - (capB - z), y, capB);
        if(canFill(y, z, capB)) addState(x, y - (capB - z), capB);
        if(canFill(y, x, total)) addState(total, y - (total - x), z);
        if(canFill(z, x, total)) addState(total, y, z - (total - x));
        if(canFill(z, y, capA)) addState(x, capA, z - (capA - y));
        if(canEmpty(x, y, capA)) addState(0, x + y, z);
        if(canEmpty(x, z, capB)) addState(0, y, x + z);
        if(canEmpty(y, z, capB)) addState(x, 0, y + z);
        if(canEmpty(y, x, total)) addState(x + y, 0, z);
        if(canEmpty(z, x, total)) addState(x + z, y, 0);
        if(canEmpty(z, y, capA)) addState(x, y + z, 0);
    }
    cout << (minSteps == INF ? "NO" : to_string(minSteps)) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin >> total >> capA >> capB) {
        if(!total && !capA && !capB) break;
        memset(steps, 0, sizeof(steps));
        stateQueue = queue<CupState>();
        if(total % 2) cout << "NO\n";
        else bfs();
    }
}