문제를 그래프로 해석하기 (BOJ 14867 물통)

Sol1) (DP - 실패)

처음 이 문제를 봤을땐, 점화식을 세워서 DP로 풀 수 있을 줄 알았다.

그러나, 직접 점화식을 구해보니, 경우의 수가 너무 많았다.

점화식 세우기:
a,b > 0 이라고 할 때,

1. [0][0]
시작지점; 무조건 0

2. [a][0]
- A 채우기; F(A)
[a][0], [a-1][0], .... [1][0], [0][0]
- B 비우기; E(B)
[a][b], [a][b-1], .... [a][1], [a][0]
- M(B,A)
[c][d] (A-c >= d; A의 남은 공간이 B의 현재 물 양보다 많은 경우)

3. [0][b]
2번에서 A,B 바꾸면

4. [a][b]
- A를 채우는 경우
[0][b], [1][b], ... , [a-1][b], [a][b]
- B를 채우는 경우
[a][0], [a][1], ... , [a][b-1], [a][b]
- M(A,B)
이 경우엔 b = B (max)
[c][d] (B-d < c; B의 남은 공간이 A의 물 양보다 적음)
- M(B,A)
a = A (max)
[c][d] (A-c < d)

 

보다시피 경우의 수가 너무 많다. 식으로 구현하기 힘들 듯

---

Sol2) (구현/시뮬레이션 - 성공)

이후 직접 DP 테이블 그려가며, 각 연산이 물 상태를 어떻게 바꾸는지 알아보려다 다음과 같은 패턴을 찾았다.

이 문제에서는 테이블의 '가장자리' 값만 답으로 나올 수 있으며,

각각 연산은 테이블에서 아래의 그림처럼 표시된다는 것이다.

 

Empty 연산과 Fill 연산. 쉽게 말해, 반대편 가장자리로 옮기는 역할. 

M(A,B) 연산. ㄴ자 가장자리에 있는 값들을 ㄱ자 가장자리로 옮긴다.

M(B,A) 연산. 반대로, ㄱ자 가장자리에 있는 값들을 ㄴ자 가장자리로 옮긴다.

Fill/Empty는 현재 노드를 반대편 가장자리로 수직으로 옮긴다는 점에서 동일하므로, 하나의 연산으로 묶었다.

Move는 ㄱ자 가장자리에 위치한 값들을 ㄴ자 가장자리에 옮기거나, 그 반대의 연산을 한다.

언뜻 보면 transpose 같지만, 테이블이 직사각형이고 matrix dimension을 바꾸지 않고 값만 가장자리로 옮긴다는 점에서 다르다.

auto M = [&](int a, int b)->pii{
    // Case 1. ㄱ 자 가장자리; M(B,A)
    if (a == 0 || b == B) {
        if (b < A - a)
            return { a + b, 0 };
        else
            return { A, b - (A - a) };
    }
    // Case 2. ㄴ자 가장자리; M(A,B)
    else {
        if (a < B - b)
            return { 0, a + b };
        else
            return { a - (B - b), B };
    }
};

auto ForE = [&](int a, int b)->pii {
    // Fill
    if (a == 0)
        return { A,b };
    else if (b == 0)
        return { a,B };
    // Empty
    else if (a == A)
        return { 0,b };
    else if (b == B)
        return { a,0 };
};

 

답을 구하는 방법은 다음과 같다.

목표 상태에서 시작해서 ForE와 M 연산을 번갈아가며 역으로 타고가다보면, (0,0)을 거치는 경우가 있고, 자기 자신으로 돌아오는 경우가 있다. 전자는 답 후보가 될 수 있는거고, 후자는 (0,0) 까지의 경로가 없는 것으로 판단하여 -1을 출력하면 된다.

 

한 지점에서 가능한 연산이 Fill/Empty 와 Move가 있기에, 두 가지 시작 루트가 있다. 

각 루트에서 나온 count 값 중 더 작은게 답이 된다.

만약 (0,0)까지의 경로가 없으면, 두 루트가 처음 위치에서 서로 연결된다.

 

결론은, 목표 지점에서 테이블을 타고 왔다갔다 이동해서 (0,0)을 거치는지 확인하는 시뮬레이션 방식으로 풀었다.

---

Sol3) (BFS - 성공)

Sol1에서 봤다시피, 물통을 채우고 비우고 옮기는 규칙을 짜기엔, 물통의 상태로 가능한 경우의 수가 너무 많다.

그럼 차라리, 모든 경우의 수를 탐색하는 건 어떨까?

 

우리는 현재 물통들의 상태를 하나의 노드라고 볼 수 있다.

그리고 현재 노드로부터 총 6가지 연산 가능하고, 각 연산은 물통의 상태를 변화시킨다. 즉, 현재 노드를 다른 노드로 변화시킨다.
여기서, 각 연산을 그래프의 다음 노드로 가는 unweighted 간선이라고 생각할 수 있다.

 

따라서, 우리 목표는 (0,0)에서 출발해서 (a,b) 노드까지의 최단 거리 찾는 것.
간선의 weight가 모두 동일한 그래프에서 BFS 사용할 시, (a,b)에 처음 다다르는 순간이 무조건 최단 거리이다.

 

각 물통의 상태를 노드, 연산을 다른 노드로의 unweighted 간선이라고 볼 수 있다. (0,0)에서 (a,b)로의 최단거리 찾는게 목표!

 

빨간색 노드처럼, 중간중간에 중복되는 노드들이 많이 섞여있을 것이다.

visited로 이들을 걸러내면서 BFS를 진행하면, 목표인 파란색 노드까지의 최단거리를 구할 수 있을 것이다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

#define X first
#define Y second

using pii = pair<int, int>;
using vii = vector<pii>;
using p = pair<pii, int>;
const int INF = int(1e9);

set<pii> visited; // 같은 좌표인지 확인만 하면 됨. set 사용
int A, B;

// 현재 노드 cur에 6가지 연산을 적용하여 다음 노드를 구한 후, v에 삽입한다. 반환값 없음
void apply_ops(vii& v, pii cur) {
    int a = cur.X, b = cur.Y;

    // Fill
    v.push_back({ A,b });
    v.push_back({ a,B });

    // Empty
    v.push_back({ 0,b });
    v.push_back({ a,0 });

    // Move
    // M(B,A)
    if (b < A - a)
        v.push_back({ a + b, 0 });
    else
        v.push_back({ A, b - (A - a) });

    // M(A,B)
    if (a < B - b)
        v.push_back({ 0, a + b });
    else
        v.push_back({ a - (B - b), B });
}

// 목표 지점까지 최단거리 반환
int BFS(int goal_x, int goal_y) {
    queue<p> q;
    q.push({ {0, 0}, 0 });
    visited.insert({ 0,0 });
    vii nxt_nodes;
    while (q.size()) {
        p tmp = q.front(); q.pop();
        pii cur = tmp.first; int x = cur.X, y = cur.Y;
        int dist = tmp.second;

        if (x == goal_x && y == goal_y) {
            return dist;
        }

        apply_ops(nxt_nodes, cur); // fills 'nxt_nodes' with next nodes

        while(!nxt_nodes.empty()){
            pii nxt = nxt_nodes.back(); nxt_nodes.pop_back();
            int x_next = nxt.X;
            int y_next = nxt.Y;

            // visited check
            auto itr = visited.find({ x_next, y_next });
            if (itr != visited.end()) {
                continue; // already visited
            }

            visited.insert({x_next, y_next});
            q.push({{ x_next, y_next }, dist+1});
        }
    }

    return -1;
}

int main() {
#ifdef DBG
    freopen("input.txt", "r", stdin);
#endif
    fastio;

    int a,b;
    cin >> A >> B >> a >> b;

    int result = BFS(a, b);

    cout << result;
    return 0;
}

 

배운 점 - 문제를 그래프로 해석해서 그래프 탐색 알고리즘 사용하는 것