[BFS,DFS] 2251번 물통

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

BFS와 DFS 참고 문제집 : https://www.acmicpc.net/workbook/view/2096

※이 문제 어떻게 풀지?※

1. BFS와 Queue를 이용하여 모든 경우의 수를 다 해볼 수 있는 상황을 연출 하였습니다.

단, 이걸 하면서 어떻게 해야할지는 알겠는 데... 구현을 하기에는 좀 힘이 들었습니다.

아직도 제 실력은 부족한 것을 많이 느꼈습니다.

※필요 역량 정리하기!!!※

1. pair, make_pair 함수를 사용할 때 => #include<utility>를 사용해 주자!!

 - 백준에서는 C++ 컴파일 에러가 나기 때문... 시험장가서도 똑같겠죠...

2. 결국 BFS...!!  밑에 소스는 <BFS + Queue>

3. sort함수에 대해서 알고 가자 => #include<algorithm>

 - sort( [배열] , [정렬할 배열 크기]);

/*
2251번 물통 

결국은 전체 탐색으로 bfs를 사용한 것일 뿐

그래프와 같다고 생각한다.
*/
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
 
int A, B, C;
bool map[202][202], ans[202];
 
struct Data { // 큐에 3가지 데이터를 넣을 때. 구조체를 이용하자
    int a, b, c;
};
 
//대문자 A,B,C 는 각 물통에 담을 수 있는 물의 최대용량
//소문자 a,b,c 는 현재 물통에 담아져 있는 물의 용량
//map[a의 물의 양][b의 물의 양]
 
void bfs() {
    queue<Data> q;
    q.push({0,0,C});
    while (!q.empty()) {
        Data now = q.front();
        q.pop();
        if (map[now.a][now.b]) // 이부분 잘 모르겠다.
            continue;
        map[now.a][now.b] = true;
 
        if (now.a == 0)
            ans[now.c] = true;
 
        //a->b
        if (now.a + now.b > B)
            q.push({ (now.a + now.b) - B,B,now.c });
        else
            q.push({ 0,now.a + now.b,now.c });
 
        //a->c
        if (now.a + now.c > C)
            q.push({ (now.a + now.b) - C,now.b,C });
        else
            q.push({ 0,now.b,now.a + now.c });
 
        //b->a
        if (now.b + now.a > A)
            q.push({ A,(now.b + now.a) - A,now.c });
        else
            q.push({ now.b + now.a, 0, now.c });
 
        //b->c
        if (now.b + now.c > C)
            q.push({ now.a,(now.b + now.c) - C,C });
        else
            q.push({ now.a, 0, now.b + now.c });
 
        //c->a
        if (now.c + now.a > A)
            q.push({ A,now.b,(now.c + now.a) - A });
        else
            q.push({ now.c + now.a,now.b,0 });
 
        //c->b
        if (now.c + now.b > B)
            q.push({ now.a,B,(now.c + now.b) - B });
        else
            q.push({ now.a,now.c + now.b,0 });
    }
}
 
int main() {
    cin >> A >> B >> C;
    bfs();
 
    sort(ans, ans + C);
    for (int i = 0; i <= C; i++)
    {
        if (ans[i])
            printf("%d ", i);
    }
    return 0;
}