[백준] 2251번 물통

2251 물통

문제

---

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

---

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

---

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

---

풀이)

나올 수 있는 모든 경우를 bfs를 통해 다 확인해보는 문제였다.

변수를 너무 많이 만들어놨더니 코드 쓰면서도 햇갈렸던 문제다.

자세히 설명하자면

물을 옮기는 경우를 전체적으로 총 6가지로 생각했다.

1. A물통에서 B물통으로 옮기기

2. A물통에서 C물통으로 옮기기

3. B물통에서 A물통으로 옮기기

4. B물통에서 C물통으로 옮기기

5. C물통에서 A물통으로 옮기기

6. C물통에서 B물통으로 옮기기

근데, 문제에서 물을 옮길 수 있는 경우는 다른 물통이 가득 차거나 한 물통이 비울 때 가능하다고 하였으니

또 세부적으로 나누었다.

(예를 들자면)

1. A물통에서 B물통으로 옮길때

  1.1 B물통이 가득 찰 경우

  1.2 A물통이 빌 경우

이런 식으로 6*2= 12가지를 모두 확인했다.

중복되는 물통들의 상태가 queue에 들어가는 것을 방지하기 위해서는 bool visited[][][] 3차원 배열을 사용했다.

visited[a][b][c] 가 true라는 뜻은 A물통이 a, B물통이 b, C물통이 c만큼의 물을 가지고 있는 상태를 이미 확인했다 라는 뜻.

그리고 A물통이 비었을때, C물통의 물 양을 출력하기 위해

vector <int> result와 bool check[]를 선언하였다.

삽입전 check[]를 통해 이전에 result에 삽입된 값인지 확인해 준 뒤, C물통의 값을 result에 삽입해주었다.

(풀이를 쓰고 나서도 느끼지만, 모든 상태를 다 보다보니 정말 더럽게 구현된 것 같다.)

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int bottle[4];//물통사이즈
vector <int> result;
bool visited[201][201][201];
bool check[201];
struct water
{
    int w1, w2, w3;
};
 
void bfs(water tmp) {
    queue <water> qu;
    qu.push(tmp);
    while (!qu.empty())
    {
        water w = qu.front();
        qu.pop();
        if (w.w1 == 0 && check[w.w3] == false) {
            check[w.w3] = true;
            result.push_back(w.w3);
        }
        //A물통에서 B물통으로 줄때
        if (w.w1 + w.w2 > bottle[2]) { //B물통이 가득 찰 경우
            if (visited[w.w1 + w.w2 - bottle[2]][bottle[2]][w.w3] == false) {
                visited[w.w1 + w.w2 - bottle[2]][bottle[2]][w.w3] = true;
                qu.push({ w.w1 + w.w2 - bottle[2],bottle[2],w.w3 });
            }
        }
        else { //A물통이 빌 경우
            if (visited[0][w.w1 + w.w2][w.w3] == false) {
                visited[0][w.w1 + w.w2][w.w3] = true;
                qu.push({ 0,w.w1 + w.w2,w.w3 });
            }
        }
        //A물통에서 C물통으로 줄때
        if (w.w1 + w.w3 > bottle[3]) { //C물통이 가득 찰 경우
            if (visited[w.w1 + w.w3 - bottle[3]][w.w2][bottle[3]] == false) {
                visited[w.w1 + w.w3 - bottle[3]][w.w2][bottle[3]] = true;
                qu.push({ w.w1 + w.w3 - bottle[3],w.w2,bottle[3] });
            }
        }
        else { //A물통이 빌 경우
            if (visited[0][w.w2][w.w1 + w.w3] == false) {
                visited[0][w.w2][w.w1 + w.w3] = true;
                qu.push({ 0,w.w2,w.w1 + w.w3 });
            }
        }
        //B물통에서 A물통으로 줄때
        if (w.w1 + w.w2 > bottle[1]) { //A물통이 가득 찰 경우
            if (visited[bottle[1]][w.w2 + w.w1 - bottle[1]][w.w3] == false) {
                visited[bottle[1]][w.w2 + w.w1 - bottle[1]][w.w3] = true;
                qu.push({ bottle[1],w.w2 + w.w1 - bottle[1],w.w3 });
            }
        }
        else { //B물통이 빌 경우
            if (visited[w.w1+w.w2][0][w.w3] == false) {
                visited[w.w1 + w.w2][0][w.w3] = true;
                qu.push({w.w1 + w.w2,0,w.w3 });
            }
        }
        //B물통에서 C물통으로 줄때
        if (w.w2 + w.w3 > bottle[3]) { 
            if (visited[w.w1][w.w2 + w.w3 - bottle[3]][bottle[3]] == false) {
                visited[w.w1][w.w2 + w.w3 - bottle[3]][bottle[3]] = true;
                qu.push({ w.w1,w.w2 + w.w3 - bottle[3],bottle[3] });
            }
        }
        else { 
            if (visited[w.w1][0][w.w2 + w.w3] == false) {
                visited[w.w1][0][w.w2 + w.w3] = true;
                qu.push({ w.w1,0,w.w2 + w.w3 });
            }
        }
        //C물통에서 A물통 줄 때
        if (w.w1 + w.w3 > bottle[1]) {
            if (visited[bottle[1]][w.w2][w.w3 + w.w1 - bottle[1]] == false) {
                visited[bottle[1]][w.w2][w.w3 + w.w1 - bottle[1]] = true;
                qu.push({ bottle[1],w.w2 ,w.w3 + w.w1 - bottle[1] });
            }
        }
        else { 
            if (visited[w.w1 + w.w3][w.w2][0] == false) {
                visited[w.w1 + w.w3][w.w2][0] = true;
                qu.push({ w.w1 + w.w3,w.w2,0 });
            }
        }
        //C물통에서 B물통 줄때
        if (w.w2 + w.w3 > bottle[2]) {
            if (visited[w.w1][bottle[2]][w.w3 + w.w2 - bottle[2]] == false) {
                visited[w.w1][bottle[2]][w.w3 + w.w2 - bottle[2]] = true;
                qu.push({ w.w1, bottle[2], w.w3 + w.w2 - bottle[2] });
            }
        }
        else {
            if (visited[w.w1][w.w2 + w.w3 + w.w3][0] == false) {
                visited[w.w1][w.w2][0] = true;
                qu.push({ w.w1,w.w2 + w.w3,0 });
            }
        }
    }
 
}
int main() {
    for (int i = 1; i <= 3; i++) {
        scanf("%d", &bottle[i]);
    }
    water tmp{ 0,0,bottle[3] };
    check[bottle[3]] = true;
    visited[0][0][bottle[3]] = true;
    result.push_back(bottle[3]);
    bfs(tmp);
    sort(result.begin(), result.end());//오름차순정렬
    for (int i = 0; i < result.size(); i++) {
        printf("%d ", result[i]);
    }
 
    return 0;
}