취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8100번 문제인 Containers이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8100

현재 네 병에 담겨있는 물의 양을 4-tuple로 생각하자. 단, 없는 병의 경우 부피가 0인 병에 0인 물이 채워져있다고 생각하자.

이 때, 각 상태를 정점으로, 에서 한 번의 조작으로 변화할 수 있는 상태와의 관계를 (방향이 있는) 간선으로 생각하면 주어진 문제는 모든 병이 꽉 찬 초기상태에서 주어진 목표 상태까지의 최단거리(단, 모든 간선의 가중치는 1)를 구하는 문제로 모델링할 수 있다.

가능한 조작이 많으므로 누락되는 조작이 없게 유의하여 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int N;
int A, B, C, D, eA, eB, eC, eD, dist[50][50][50][50];
queue<pair<pair<int, int>, pair<int, int>>> que;

void bfs() {
    dist[A][B][C][D] = 1;
    que.push({{A, B}, {C, D}});
    while (!que.empty()) {
        int a = que.front().first.first, b = que.front().first.second, c = que.front().second.first, d = que.front().second.second; que.pop();
        if (!dist[0][b][c][d]) dist[0][b][c][d] = dist[a][b][c][d] + 1, que.push({{0, b}, {c, d}});
        if (!dist[a][0][c][d]) dist[a][0][c][d] = dist[a][b][c][d] + 1, que.push({{a, 0}, {c, d}});
        if (!dist[a][b][0][d]) dist[a][b][0][d] = dist[a][b][c][d] + 1, que.push({{a, b}, {0, d}});
        if (!dist[a][b][c][0]) dist[a][b][c][0] = dist[a][b][c][d] + 1, que.push({{a, b}, {c, 0}});
        int val;
        val = min(B - b, a);
        if (!dist[a - val][b + val][c][d]) dist[a - val][b + val][c][d] = dist[a][b][c][d] + 1, que.push({{a - val, b + val}, {c, d}});
        val = min(A - a, b);
        if (!dist[a + val][b - val][c][d]) dist[a + val][b - val][c][d] = dist[a][b][c][d] + 1, que.push({{a + val, b - val}, {c, d}});
        val = min(C - c, a);
        if (!dist[a - val][b][c + val][d]) dist[a - val][b][c + val][d] = dist[a][b][c][d] + 1, que.push({{a - val, b}, {c + val, d}});
        val = min(A - a, c);
        if (!dist[a + val][b][c - val][d]) dist[a + val][b][c - val][d] = dist[a][b][c][d] + 1, que.push({{a + val, b}, {c - val, d}});
        val = min(D - d, a);
        if (!dist[a - val][b][c][d + val]) dist[a - val][b][c][d + val] = dist[a][b][c][d] + 1, que.push({{a - val, b}, {c, d + val}});
        val = min(A - a, d);
        if (!dist[a + val][b][c][d - val]) dist[a + val][b][c][d - val] = dist[a][b][c][d] + 1, que.push({{a + val, b}, {c, d - val}});
        val = min(C - c, b);
        if (!dist[a][b - val][c + val][d]) dist[a][b - val][c + val][d] = dist[a][b][c][d] + 1, que.push({{a, b - val}, {c + val, d}});
        val = min(B - b, c);
        if (!dist[a][b + val][c - val][d]) dist[a][b + val][c - val][d] = dist[a][b][c][d] + 1, que.push({{a, b + val}, {c - val, d}});
        val = min(D - d, b);
        if (!dist[a][b - val][c][d + val]) dist[a][b - val][c][d + val] = dist[a][b][c][d] + 1, que.push({{a, b - val}, {c, d + val}});
        val = min(B - b, d);
        if (!dist[a][b + val][c][d - val]) dist[a][b + val][c][d - val] = dist[a][b][c][d] + 1, que.push({{a, b + val}, {c, d - val}});
        val = min(D - d, c);
        if (!dist[a][b][c - val][d + val]) dist[a][b][c - val][d + val] = dist[a][b][c][d] + 1, que.push({{a, b}, {c - val, d + val}});
        val = min(C - c, d);
        if (!dist[a][b][c + val][d - val]) dist[a][b][c + val][d - val] = dist[a][b][c][d] + 1, que.push({{a, b}, {c + val, d - val}});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    if (N == 1) cin >> A >> eA;
    else if (N == 2) cin >> A >> B >> eA >> eB;
    else if (N == 3) cin >> A >> B >> C >> eA >> eB >> eC;
    else cin >> A >> B >> C >> D >> eA >> eB >> eC >> eD;
    bfs();

    if (dist[eA][eB][eC][eD]) cout << dist[eA][eB][eC][eD] - 1;
    else cout << "NIE";
}