백준 14867번 물통 - C++ 풀이

---

 

1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다.
2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다.

 

1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다.

 주어진 연산을 사용하면 항상 두 물통 중 한 물통은 꽉 차있거나 비어있어야 한다. 따라서 상태를 나타낼 때, 아래와 같은 3가지 정보만 있으면 된다.

1. 한 물통에 들어있는 양 x
2. 그 물통이 A물통인지 B물통인지 여부
3. 반대 물통이 비어있는지 꽉 차있는지 여부

두 물병에 들어있는 물의 양 정보 대신 위의 정보를 사용하여 상태를 나타내면 상태 개수를 N^2개에서 4N개로 줄일 수 있다. 

 

2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다.

 위의 사실을 이용해서 상태 노드를 나타내고 BFS를 사용해서 최단 연산 횟수를 구해주면 된다. 상태노드를 통해 현재 두 물통에 들어있는 양을 계산하여 목표 상태에 도달했는지 판단할 수 있다.

 

반응형

---

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll INF = 1e10;

struct Node {
    int bottle; // 왼쪽 물병인지 오른쪽 물병인지
    int x;      // bottle에 들어있는 양
    int full;   // 반대 물병이 비어있는지 꽉 차있는지(무조건 둘중에 하나)
};

int A, B, C, D;
ll dist[2][100001][2];
queue<Node> q;

Node toNode(int a, int b) {
    if (a == A) return {1, b, 1};
    if (a == 0) return {1, b, 0};
    if (b == B) return {0, a, 1};
    if (b == 0) return {0, a, 0};
    return {0, 0, 0};
}

void pushNext(int a, int b, int d) {
    Node next = toNode(a, b);
    
    if (dist[next.bottle][next.x][next.full] == INF) {
        dist[next.bottle][next.x][next.full] = d;
        q.push(next);
    }
}

ll BFS() {
    fill(&dist[0][0][0], &dist[0][0][0]+2*100001*2, INF);
    
    q.push({0, 0, 0});
    dist[0][0][0] = 0;
    
    while (!q.empty()) {
        Node curr = q.front(); q.pop();
        
        int bottle = curr.bottle;
        int x = curr.x;
        int full = curr.full;
        ll curr_dist = dist[bottle][x][full];
        
        int a = (bottle == 0) ? x : (full ? A : 0);
        int b = (bottle == 1) ? x : (full ? B : 0);
        
        if (a == C && b == D) return curr_dist;
        
        // fill A
        pushNext(A, b, curr_dist+1);
        // fill B
        pushNext(a, B, curr_dist+1);
        // empty A
        pushNext(0, b, curr_dist+1);
        // empty B
        pushNext(a, 0, curr_dist+1);
        // move from A to B
        pushNext(a+b-min(B, b+a), min(B, b+a), curr_dist+1);
        // move from B to A
        pushNext(min(A, a+b), a+b-min(A, a+b), curr_dist+1);
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> A >> B >> C >> D;
    cout << BFS();

    return 0;
}