처음에는 a -> b, b -> c와 같은 경로를 백트래킹을 통해 해결해보고자 하였지만 문제를 풀다 이건 백트래킹으로 해결하지 못하겠다 라는 생각이 들어 다양한 방법을 고민해보았다.

하지만 결국 답을 알지못해 정답을 찾아보았는데 그래프 이론을 통해 해결하는 문제였다. 좀 더 깊게 생각해보니 문제의 물통 갯수는 정해져있고 이는 C가 담겨있을 수 있는 물의 양의 개수가 최대 5개 라는 것이다.

지금까지 그래프이론 문제는 2중 배열을 이용한 MAP 문제만 풀어왔기에 이 문제를 그래프이론으로 접근해볼 생각을 하지 못했다.

SET

C++의 Standard Template Library (STL)에서 set은 고유한 원소를 저장하고 자동으로 정렬하는 컨테이너입니다.

그리고 SET STL을 이용해 해결하였는데 2가지 이유가 있었다. 1. 중복 방지, 2. 오름차순 정렬

문제의 답은 C 물통이 담겨지는 물의 경우의 수가 아닌 물의 양이다. 즉 10,10,10이 각각 다른 양의 물이 A ,B통에 담겨져 다른 경우더라도 답은 10 하나만 출력되야한다. 그래서 기존 VECTOR에 답을 PUSH_BACK 한뒤 SORT한 것은 정답이 되지 못했다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>

using namespace std;
int n,a;
int max_a, max_b, max_c;
bool a_visit[201] = {false};
bool b_visit[201] = {false};
bool c_visit[201] = {false};

vector<int> result;

void backtracking(char mul, int a, int b, int c) {
    if (a == 0) {
        result.push_back(c);
        return;
    }
    else {
        for (int i = 0; i < 2; i++) {
            if (mul == 'a') {
                backtracking()
            }
        }
    }
}

int main() {

    // 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
    // 백트래킹?
    // dp는 아닌거같음 a,b,c 매개변수로 넣어서 a == 0일때 c의 크기를 정답에 넣으면 될듯 이러면 a,b,c를 배열로 해서 각 무게를 visit으로 표현해야 중복방지 될듯
    // visit 중복 방지는 백트래킹하면 무조건 해얗나ㅡㄴ건데 굳이? ㅇㅋ 안함

    //물통 크기 처음에 c는 꽉차있음
    cin >> max_a >> max_b >> max_c;
    
    backtracking('c', 0, 0, 10);

    return 0;
}

정답 출처

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <set>


using namespace std;
int max_a, max_b, max_c;

bool visit[201][201][201] = { false };

set<int> result;
int mv;
int na, nb, nc;
void bfs() {

    queue < pair<pair<int, int>, int >> q;

    q.push({ {0,0},max_c });

    result.insert(max_c);

    while (!q.empty()) {

        int ia = q.front().first.first;
        int ib = q.front().first.second;
        int ic = q.front().second;
        q.pop();

        if (visit[ia][ib][ic] == true) {
            continue;
        }

        visit[ia][ib][ic] = true;

        //a에서 움직임
        if (ia != 0) {
            if (ib != max_b) {
                mv = min(ia,max_b - ib);
                na = ia - mv;
                nb = ib + mv;
                nc = ic;
                q.push({ {na,nb},nc });
                if (na == 0 && visit[na][nb][nc] == false) {
                    result.insert(nc);
                }
            }
            if (ic != max_c) {
                mv = min(ia,max_c - ic);
                na = ia - mv;
                nb = ib;
                nc = ic + mv;
                q.push({ {na,nb},nc });
                if (na == 0 && visit[na][nb][nc] == false) {
                    result.insert(nc);
                }
            }
        }

        //b에서 움직임
        if (ib != 0) {
            if (ia != max_a) {
                mv = min(ib,max_a - ia);
                na = ia + mv;
                nb = ib - mv;
                nc = ic;
                q.push({ {na,nb},nc });
                if (na == 0 && visit[na][nb][nc] == false) {
                    result.insert(nc);
                }
            }
            if (ic != max_c) {
                mv = min(ib,max_c - ic);
                na = ia;
                nb = ib - mv;
                nc = ic + mv;
                q.push({ {na,nb},nc });
                if (na == 0 && visit[na][nb][nc] == false) {
                    result.insert(nc);
                }
            }
        }

        //c에서 움직임
        if (ic != 0) {
            if (ib != max_b) {
                mv = min(ic,max_b - ib);
                na = ia;
                nb = ib + mv;
                nc = ic - mv;
                q.push({ {na,nb},nc });
                    if (na == 0 && visit[na][nb][nc] == false) {
                    result.insert(nc);
                }
            }
            if (ia != max_a) {
                mv = min(ic,max_a - ia);
                na = ia + mv;
                nb = ib;
                nc = ic - mv;
                q.push({ {na,nb},nc });
                if (na == 0 && visit[na][nb][nc] == false) {
                    result.insert(nc);
                }
            }
        }
        

    }

    for (int value : result){
        cout << value << " ";
    }


}

int main() {

    cin >> max_a >> max_b >> max_c;
 
    bfs();

    return 0;
}