(C++) - 백준(BOJ) 2251 : 물통

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

2251번: 물통

bfs문제였습니다.

📕 풀이방법

📔 입력 및 초기화

각 물통의 용량을 저장할 일차원 배열 a, 방문 여부를 저장할 3차원 배열 ck, 정답을 저장할 vector v를 선언 후 입력받습니다.

📔 풀이과정

A, B, C에 담긴 물의 용량을 각각 x,y,z라고 한다면 물을 붓는 상태는 다음과 같이 6가지가 됩니다. 각 상태에는 또 부었을 때 물이 넘치는 경우와 그렇지 않은 경우, 두 가지로 나뉩니다.

1. x -> y

2. x -> z

 

3. y -> x

4. y -> z

 

5. z -> x

6. z -> y

A가 비어있을 때 c의 용량을 v에 push해줍니다.

📔 정답출력

v의 원소를 오름차순으로 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int,int,int>;
int a[3], ck[201][201][201];
vector <int> v;

void bfs(){
    queue <tiii> q;
    q.push({0,0,a[2]});

    while(!q.empty()){
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int z = get<2>(q.front());
        q.pop();
        if(ck[x][y][z]) continue;
        ck[x][y][z] = 1;
        if(!x) v.push_back(z);

        if(x + y > a[1]) q.push({x -(a[1] - y), a[1], z});
        else q.push({0, x + y, z});

        if(x + z > a[2]) q.push({x-(a[2] - z), y, a[2]});
        else q.push({0, y, x+z});

        if(y + x > a[0]) q.push({a[0],y-(a[0]-x),z});
        else q.push({y+x, 0, z});

        if(y + z > a[2]) q.push({x,y-(a[2]-z),a[2]});
        else q.push({x, 0, y+z});
        
        if(z + x > a[0]) q.push({a[0],y, z - (a[0]-x)});
        else q.push({z+x,y,0});

        if(z + y > a[1]) q.push({x, a[1],z - (a[1] - y)});
        else q.push({x, z+y, 0});
    }
}

int main(){
    for(int i = 0; i < 3; i++) cin >> a[i];
    bfs();
    sort(v.begin(), v.end());
    for(auto e : v) cout << e << ' ';
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.