[백준 14867] 물통 (C++)

14867번: 물통

 

방문 여부를 체크하는 BFS 문제이다.

물의 용량이 100000, 100000 이므로 배열로 체크하진 못하고, map 자료형을 사용해서 체크할 수 있다.

 

bfs를 수행하면서 큐에 상태를 넣기 위한 조건이 있다.

• A에 물을 가득 채우기
• B에 물을 가득 채우기
• A를 비우기
• B를 비우기
• A->B로 물 이동
• B->A로 물이동

현재 상태로부터 총 6가지의 상태로 변화할 수 있다.

 

하지만 bfs의 특성상 다음 상태가 이미 나온적이 있는 상태라면 해당 상태부터 다시 탐색할 필요가 없기 때문에 넘어간다.

 

A->B, B->A인 경우 문제에서 주어진대로 구현을 해서 물의 용량을 결정해주면 된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>

typedef long long ll;
// typedef pair<int, int> pii;

using namespace std;

struct State{
    pii st;
    int cnt;
};

int A, B, C, D;
map<pii, int> visited;

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

void bfs(){
    int answer = INF;
    
    pii start = {0, 0};
    queue<State> que;
    que.push({start, 0});
    visited[start] = 1;
    
    while(!que.empty()){
        pii now = que.front().st;
        int now_cnt = que.front().cnt;
        que.pop();
        pii _next;
        
        if(now.first == C && now.second == D){
            answer = min(answer, now_cnt);
        }
        
        // A물통을 가득 채우는 경우
        _next = {A, now.second};
        if(!visited[_next]){
            visited[_next] = 1;
            que.push({_next, now_cnt+1});
        }
        
        // B물통을 가득 채우는 경우
        _next = {now.first, B};
        if(!visited[_next]){
            visited[_next] = 1;
            que.push({_next, now_cnt+1});
        }
        
        // A를 모두 버리는 경우
        _next = {0, now.second};
        if(!visited[_next]){
            visited[_next] = 1;
            que.push({_next, now_cnt+1});
        }
        
        // B를 모두 버리는 경우
        _next = {now.first, 0};
        if(!visited[_next]){
            visited[_next] = 1;
            que.push({_next, now_cnt+1});
        }
        
        // A -> B로 이동
        int b_left = B - now.second;
        if(now.first >= b_left) _next = {now.first - b_left, B};
        else _next = {0, now.first + now.second};
        if(!visited[_next]){
            visited[_next] = 1;
            que.push({_next, now_cnt+1});
        }
        
        // B -> A로 이동
        int a_left = A - now.first;
        if(now.second >= a_left) _next = {A, now.second - a_left};
        else _next = {now.first + now.second, 0};
        if(!visited[_next]){
            visited[_next] = 1;
            que.push({_next, now_cnt+1});
        }
    }
    
    if(answer == INF) cout << -1;
    else cout << answer;
}

void solve(){
    bfs();
}

int main(){
    input();
    solve();
    
    return 0;
}