[ 백준 ] 2251 / 물통

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
156/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2251 / 물통
 *
 * Kind :: BFS
 *
 * Insight
 * - 중간 상태를 용량 A, B, C 물통들에 각각 차있는 물의 양이라고 했을 때
 *   가능한 모든 상태는 201^3 이다 <= (0~200) * (0~200) * (0~200)
 *   + 그러나 차있는 물의 양의 총합은 언제나 C이다
 *     즉, 두 물통에 각각 차있는 물의 양을 알면 나머지 한 물통에 차있는 물의 양을 알 수 있다
 *     그러므로 가능한 상태는 200^2 가 된다
 *     # 모든 가능한 상태를 탐색해봐도 시간 제한내에 풀 수 있을 것 같다
 *       굳이 이전의 상태를 기억할 필요는 없으니 BFS 로 구현했다
 *
 * - 용량 A, B, C 물통들에 각각 차있는 물의 양을 a, b, c 라고 하자
 *   이때, 용량 A 물통을 용량 C 물통으로 쏟아 붓는 상황이라고 하자
 *   + 위를 구현하는 방식은 다양할 것 같은데...
 *     그냥 일단
 *     c = a + b
 *     a = 0
 *     으로 만들어준다 <= 물통의 용량 생각없이 붓고 본다
 *     # 그리고 나서 물통의 용량을 고려해준다
 *       -> c <= C 이면 물이 넘치지 않는다
 *       -> c > C 이면 (c-C) 만큼 a 에 되돌려준다
 *          a = c-C
 *          c = C
 *          이 방법이 개인적으로 제일 직관적이고 쉬운 것 같다
 *
 * Point
 * - 하드코딩하기 싫다 <= 진심으로!!!
 *   + 물통들에 들어있는 물의 양을 배열로 다루자
 *     vector<int> Status
 *     Status s = {a, b, c}
 *     # index 0 - 용량 A 물통에 차 있는 물의 양
 *       index 1 - 용량 B 물통에 차 있는 물의 양
 *       index 2 - 용량 C 물통에 차 있는 물의 양
 *       -> 이렇게 하면 일일이 모든 경우를 열거하지 않고
 *          for 문으로 쏟을 물통과 받을 물통을 다룰 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <set>

using namespace std;

#define endl '\n'

// Set up : Global Variables
typedef vector<int> Status;

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int A, B, C;
    cin >> A >> B >> C;

    // Process
    Status v = {A, B, C}; /* 각 물통들의 용량 */

    bool isVisited[A+1][B+1];
    memset(isVisited, false, sizeof(isVisited));

    queue<Status> que;
    que.push(vector<int>({0,0,C})); /* 초기상태는 세 번째 물통에만 물이 가득 차있음 */
    isVisited[0][0] = true;

    set<int> ans; /* 첫 번째 물통이 비어 있을 때
                   * 세 번째 물통에 담길 수 있는 물의 양들을 저장한 Set */
    while (not(que.empty())) {
        Status c = que.front(); que.pop(); /* 현재 물통들의 상태 */
        /* c[0] - 첫 번째 물통에 들어있는 물의 양
         * c[1] - 두 번째 물통에 들어있는 물의 양
         * c[2] - 세 번째 물통에 들어있는 물의 양 */
        if (c[0] == 0) { /* 첫 번째 물통이 비어있으면 */
            ans.insert(c[2]); /* 세 번째 물통의 물의 양을 ans 에 저장 */
        }

        for (int f=0; f<=2; f++) { /* f = 쏟을 물통의 index */
            for (int t=0; t<=2; t++) { /* t = 받을 물통의 index */
                if (f == t) continue; /* 쏟을 물통과 받을 물통이 같을 수는 없음 */
                Status n = c; /* 다음 상태 */
                n[t] += n[f]; /* 일단 쏟고봄 */
                n[f] = 0;
                if (n[t] > v[t]) { /* 받은 물통의 물이 넘치면
                                    * 넘친 물 만큼 쏟은 물통에 다시 넣어줌 */
                    n[f] += n[t]-v[t];
                    n[t] = v[t];
                }
                /* 다음 상태가 이전에 방문한 적 있는 상태가 아니면 */
                if (not(isVisited[n[0]][n[1]])) { 
                    isVisited[n[0]][n[1]] = true; /* 방문 */
                    que.push(n);
                }
            }
        }
    }

    // Control : Output
    for (int n : ans) {
        cout << n << ' ';
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글