[BOJ 2251] 물통

문제

물통

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

 

 

풀이

설명

규칙에 따라 물을 옮겼을 때, C에 담겨있을 수 있는 물의 양을 모두 구하는 문제입니다.

 

규칙은 다음과 같습니다.

• 처음에 앞의 두 물통(A, B)은 비어있고, 세 번째 물통(C)은 가득 차 있습니다.
• 어떤 물통에 들어있는 물을 다른 물통에 부을 수 있습니다.
  
  • 이때, 한 물통이 비거나, 다른 한 물통이 가득찰 때까지 물을 부을 수 있습니다.
• 첫 번째 물통이 비어 있을 때, 세 번째 물통에 담겨있을 수 있는 물의 양을 구합니다.

 

모든 경우의 수를 체크하면 되므로, 그래프 탐색을 통해 해결할 수 있습니다.

 

예시 코드

function solution() {
  const [A, B, C] = input().split(" ").map(Number);
  const queue = new Queue();
  const visited = new Set();
  const answer = new Set();

  queue.enqueue([0, 0, C]);

  while (!queue.isEmpty()) {
    const [a, b, c] = queue.dequeue();
    const key = `${a},${b},${c}`;

    if (visited.has(key)) continue;
    visited.add(key);

    if (a === 0) answer.add(c);

    let water = 0;
    // A to B
    water = Math.min(a, B - b);
    queue.enqueue([a - water, b + water, c]);
    // A to C
    water = Math.min(a, C - c);
    queue.enqueue([a - water, b, c + water]);
    // B to A
    water = Math.min(b, A - a);
    queue.enqueue([a + water, b - water, c]);
    // B to C
    water = Math.min(b, C - c);
    queue.enqueue([a, b - water, c + water]);
    // C to A
    water = Math.min(c, A - a);
    queue.enqueue([a + water, b, c - water]);
    // C to B
    water = Math.min(c, B - b);
    queue.enqueue([a, b + water, c - water]);
  }

  return [...answer]
    .map((v) => Number(v))
    .sort((a, b) => a - b)
    .join(" ");
}