2251번 - 물통(c++)

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

 

세 개의 물통 A, B, C가 있다. A, B, C 물통의 용량이 주어지고, 처음에는 C 물통에만 물이 가득 차 있다.
이때 A 물통이 비어 있을 때, C 물통에 담겨 있을 수 있는 물의 양을 모두 구하는 문제다.

 

물이 다양하게 담겨있는 여러가지 경우의 수 를 따지는 BFS(너비 우선 탐색) 방법을 이용하는 문제다.

---

핵심 아이디어

• 상태 표현
  (A, B, C) 세 물통에 들어 있는 물의 양으로 상태를 표현한다.
  하지만 세 개 다 저장할 필요는 없다.
  왜냐하면 C = 전체 물의 양 - (A+B)로 항상 계산할 수 있기 때문이다.
  따라서 (A, B) 두 값만 저장하면 충분하다.
• 상태 전이(물 붓기)
  물을 옮기는 경우의 수는 6가지다.
  • A→B, A→C, B→A, B→C, C→A, C→B
    출발 물통의 물을 도착 물통에 다 붓는다고 가정한다.
    만약 넘친다면, 넘친 만큼은 다시 출발 물통에 남겨둔다.
• 정답 조건
  A가 비어 있을 때, C에 담긴 물의 양을 기록한다.
  나중에 기록된 값을 모두 출력하면 된다.

---

고민했던 부분

처음엔 정답을 저장하려면 vector에 push_back해서 나중에 정렬하면 되지 않을까? 라고 생각했다.
문제에서 가능한 C의 값은 0~200 사이로 한정되어 있다.
즉, bool answer[201] 배열을 두고 체크만 해주면 훨씬 간단하다.

• 배열을 쓰면 → 자동으로 중복 제거 + 정렬 불필요
• 벡터를 쓰면 → 나중에 정렬 + 중복 제거 과정이 필요

문제 크기상 배열이 더 효율적이라는 걸 이해할 수 있었다.

 

사실 문제 전반적으로 BFS를 쓰는것까진 알았지만 방문배열은 어떻게 설정할지, 물을 옮기는걸 어떻게 구현할지 감이 잘 안왔던

어려웠던 문제다. 그래서 책에 나온 답안을 보고 분석해서 주석을 달아봤다. 완성된 코드를 분석할때는 머릿속에 데이터 흐름도 잘 그려지고 코드 이해도 잘 되고 왜 이 정답코드에선 배열을 이렇게 선언하고 어떤건 저렇게 하고 의도가 다 이해가 되는데 왜 직접 응용하려하면 어려운지 모르겠다.

---

정답 코드

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

using namespace std;

void BFS();

// 물을 붓는 6가지 경우를 정의
// 0: A, 1: B, 2: C 라고 했을 때
// Sender[k] -> Receiver[k] 로 물을 옮김
static int Sender[] = { 0, 0, 1, 1, 2, 2 };
static int Receiver[] = { 1, 2, 0, 2, 0, 1 };

// 방문 배열: visited[A][B]
// A와 B의 물의 양이 정해지면, C는 자동으로 결정되므로 2차원만 쓰면 됨
static bool visited[201][201];

// 답을 저장할 배열: answer[c] = true → C에 물이 c만큼 있을 수 있음
static bool answer[201];

// now[0], now[1], now[2] → 각 물통의 최대 용량
static int now[3];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> now[0] >> now[1] >> now[2];

    BFS();

    for (int i = 0; i < 201; i++) {
        if (answer[i]) cout << i << " ";
    }
}

void BFS() {
    // (A, B)의 상태만 저장 → C는 전체 - (A+B)로 알 수 있음
    queue<pair<int, int>> queue;

    // 시작 상태: A=0, B=0 (C=now[2], 즉 가득 참)
    queue.push(make_pair(0, 0));
    visited[0][0] = true;

    // 처음 상태에서 C의 물 양을 답 후보에 추가
    answer[now[2]] = true;

    // BFS 탐색 시작
    while (!queue.empty()) {
        pair<int, int> p = queue.front();
        queue.pop();

        // 현재 상태 (A, B)
        int A = p.first;
        int B = p.second;

        // C는 전체에서 A와 B를 빼면 됨
        int C = now[2] - A - B;

        // 6가지 경우의 물 붓기를 모두 시도
        for (int k = 0; k < 6; k++) {
            // next[] = {A, B, C} 현재 상태 복사
            int next[] = { A, B, C };

            // Sender에서 Receiver로 물을 전부 붓는다
            next[Receiver[k]] += next[Sender[k]];
            next[Sender[k]] = 0;

            // 만약 Receiver가 넘치면 조정
            if (next[Receiver[k]] > now[Receiver[k]]) {
                // 초과한 만큼 Sender에 다시 담아준다
                next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]];
                // Receiver는 최대치까지만 채운다
                next[Receiver[k]] = now[Receiver[k]];
            }

            // (A, B) 상태가 아직 방문되지 않았다면
            if (!visited[next[0]][next[1]]) {
                visited[next[0]][next[1]] = true;
                queue.push(make_pair(next[0], next[1]));

                // A가 비어있을 때, C의 값은 답 후보에 기록
                if (next[0] == 0) {
                    answer[next[2]] = true;
                }
            }
        }
    }
}