[백준/c++] 2251번: 물통

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

2251번: 물통

 

문제 요약

 

"처음에는" A, B 물통 == empty, C 물통 == full

물을 이리저리 붓고 A 물통이 비었을 때, C 물통에 담겨있을 수 있는 물의 양을 순서대로 출력해라.

 

물 붓는 방법

• 붓는 물통 빌 때까지
  
  
• 채워지는 물통 가득 찰 때까지

 

 

범위

 

부피 A, B, C (1≤A, B, C≤200)

 

 

---

 

BFS로 풀 수 있는데, 물통 안에 들어있는 물의 양을 (a, b, c)라고 할 때, 이를 정점이라고 생각하고 가능한 물통의 양 상태에 방문해보자. 

이동할 수 있는 방법에서 조금 헷갈렸는데, 이동할 수 있는 방법은 두 가지뿐이다. 물을 붓는 물통이 비거나 채워지는 물통이 가득 채워지거나.

 

물통이 A, B, C 3개이므로 이동할 수 있는 방법이 6가지인데,

• A → B
• B → A
• A → C
• C → A
• B → C
• C → B

 

여기에서 이동방법이 두 가지 이므로 그에 맞는 조건을 적용해주면 된다.

예를 들어, A 에서 B로 물을 이동시키는 방법에 대해서 생각해보면, 여기서 a, b는 현재 A와 B에 있는 물의 양이고 A, B는 각 물통의 부피다.(최댓값)

• a + b > B : B의 물통이 가득 찬 경우 ➿ 물통 B는 B만큼의 물을 가지게 되고(full) 물통 A는 둘을 더한 값에서 B를 뺀 물을 가지게 된다(a+b-B).
  
  
• a + b <= B : A의 물통이 비게 된 경우 ➿ A의 물(a)과 B의 물(b)을 더했음에도 B를 채우지 못했다는 것이므로 물통 A는 비었고(empty) 물통 B는 둘을 더한 물을 가지게 된다(a+b).  

다른 물통의 경우에도 적용되므로 머리를 조금만 굴려주면🧛‍♀️ 구현할 수 있다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int A, B, C; //각 물통의 부피
bool visited[201][201][201];
vector<int> ans;
queue<pair<pair<int, int>,int>> q;

void input(){
    cin >> A >> B >> C;
}

void bfs(){
    q.push(make_pair(make_pair(0, 0), C)); //처음에는 A,B = empty, C = full
    while(!q.empty()){
        //a, b, c 는 각 물통의 양
        int a = q.front().first.first;
        int b = q.front().first.second;
        int c = q.front().second;
        q.pop();
        
        if(visited[a][b][c]) continue; //방문한 곳이라면 패스
        visited[a][b][c] = true;
        
        if(a==0) ans.push_back(c); //A통이 비었을 때, "C"에 담겨있을 수 있는 물의 양을 구해야 하므로
        
        if(a+b>B) q.push(make_pair(make_pair(a+b-B, B), c)); //A->B
        else      q.push(make_pair(make_pair(0, a+b), c));
        
        if(a+b>A) q.push(make_pair(make_pair(A, a+b-A), c)); //B->A
        else      q.push(make_pair(make_pair(a+b, 0), c));
        
        if(a+c>C) q.push(make_pair(make_pair(a+c-C, b), C)); //A->C
        else      q.push(make_pair(make_pair(0, b), a+c));
        
        if(a+c>A) q.push(make_pair(make_pair(A, b), a+c-A)); //C->A
        else      q.push(make_pair(make_pair(a+c, b), 0));
        
        if(b+c>C) q.push(make_pair(make_pair(a, b+c-C), C)); //B->C
        else      q.push(make_pair(make_pair(a, 0), b+c));
        
        if(b+c>B) q.push(make_pair(make_pair(a, B), b+c-B)); //C->B
        else      q.push(make_pair(make_pair(a, b+c), 0));
    }
}

void output(){
    sort(ans.begin(), ans.end());
    for(auto it = ans.begin(); it != ans.end(); it++)
        cout << *it << " ";
    cout << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    bfs();
    output();
    return 0;
}

 

 

 

 

처음에는 문제가 이해가 안돼서 다음에 하기로 미룬 문제였는데, 역시 다시 읽어보니 이해할 수 있는 문제였다... 하루에 정해진 문제의 수가 있는 것인가... 흑흑 그래도 굉장히 어려운 줄 알았는데 아니어서 다행이었다..^^!

 

+ BFS로 바로 생각이 연결되지 않아서 아쉬웠다. 다양하게 생각해보도록 노력해야겠다. 🥲

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!