2251

백준 2251번

Link: 2251번: 물통

---

문제 설명

연휴 시작한 다음날 어떻게 풀지 고민하다 방법만 생각해두고 풀진 않았던 문제.

생각했던 풀이대로 풀어봤는데 우선 틀리고 시작했다.

알고리즘 분류는 BFS로 되어 있는데 굳이 BFS를 써야하나…?? 라는 생각이 좀 들었다.

아무튼 어거지로라도 BFS로 맞춰서 풀어보니 풀렸다.

통상 아는 BFS와는 좀 다른데, 우선 3개의 물통의 양을 전부 한번에 저장해야 한다는 점이 달랐고 길찾는 BFS는 for문 돌려서 4방향정도 생각해보는게 끝인데 이건 6가지 경우를 전부 하나씩 고려해야 한다는 점이 조금 달랐다.

BFS를 이렇게도 쓸수 있구나 하는 생각이 들게 된 문제.

한가지 더 특기하자면 구조체를 직접 정의하고 활용한 첫 문제인 것 같다.

예전에 한번 3가지였나 4가지 값을 큐에 넣고 썼던 적이 있던것 같은데 그때는 make_pair를 여러번 써서 무식하게 해결했던 것 같다.

구조체에 익숙해지면 훨씬 우아한 방법으로 해결 가능할듯 하다.

연휴 내내 놀았으니 이제 다시 또 꾸준히 풀어볼 작정이다.

---

어림도 없던 코드

//
// Created by Keith_Lee on 07/02/2019.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int A, B, C;

    cin >> A >> B >> C;

    bool basket[201];

    vector<int> possible;

    if(C > 0){
        if(!basket[C]) {
            possible.push_back(C);
            basket[C] = true;
        }
    }

    if(C - (C-A) >= 0){
        if(!basket[C-A] && C-A >= 0) {
            possible.push_back(C - A);
            basket[C-A] = true;
        }
    }

    if(C - (C-B) >= 0){
        if(!basket[C-B] && C-B >= 0){
            possible.push_back(C-B);
            basket[C-B] = true;
        }
    }

    if(C - A >= 0){
        if(!basket[A]){
            possible.push_back(A);
            basket[A] = true;
        }
    }

    if(C - B >= 0){
        if(!basket[B]){
            possible.push_back(B);
            basket[B] = true;
        }
    }

    sort(possible.begin(), possible.end());

    for(int i=0; i<possible.size(); i++){
        cout << possible[i] << ' ';
    }
    cout << '\n';

    return 0;
}

---

정답 코드

//
// Created by Keith_Lee on 07/02/2019.
//

#include <iostream>
#include <queue>

using namespace std;

struct water{
    int a, b, c;
};

int A, B, C;
bool visit[201][201];
bool result[201];

void BFS(){
    queue<water> Queue;
    Queue.push({0, 0, C});

    while(!Queue.empty()){
        water current = Queue.front();
        Queue.pop();

        if(visit[current.a][current.b]){
            continue;
        }

        visit[current.a][current.b] = true;

        if(current.a == 0){
            result[current.c] = true;
        }

        if(current.a + current.b > B) { // A -> B / A + B가 B보다 크면 B는 가득, A는 A + B - B의 용량만큼 찬다.
            Queue.push({current.a + current.b - B, B, current.c});
        }
        else{ // A + B가 B보다 작으므로 A의 물을 전부 B로 붓는다.
            Queue.push({0, current.a + current.b, current.c});
        }

        if(current.a + current.b > A){ // B -> A
            Queue.push({A, current.a + current.b - A, current.c});
        }
        else{
            Queue.push({current.a + current.b, 0, current.c});
        }

        if(current.a + current.c > C){ // A -> C
            Queue.push({current.a + current.c - C, current.b, C});
        }
        else{
            Queue.push({0, current.b, current.a + current.c});
        }

        if(current.a + current.c > A){ // C -> A
            Queue.push({A, current.b, current.a + current.c - A});
        }
        else{
            Queue.push({current.a + current.c, current.b, 0});
        }

        if(current.b + current.c > C){ // B -> C
            Queue.push({current.a, current.b + current.c - C, C});
        }
        else{
            Queue.push({current.a, 0, current.b + current.c});
        }

        if(current.b + current.c > B){ // C -> B
            Queue.push({current.a, B, current.b + current.c - B});
        }
        else{
            Queue.push({current.a, current.b + current.c, 0});
        }
    }
}

int main(){
    cin >> A >> B >> C;

    BFS();

    for(int i=0; i<201; i++){
        if(result[i]){
            cout << i << ' ';
        }
    }
    cout << '\n';

    return 0;
}

---