[Algorithm] 물통 (백준 - 2251)

📋 문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

입출력 예

예제 입력	예제 출력
8 9 10	1 2 8 9 10

✏️ 풀이

이 문제는 DFS를 이용해서 풀었다. 생각하기가 조금 어려웠는데 물이 차있는 각 상황을 하나의 경우로 보고 탐색을 진행하는 방향으로 생각했다.

 

답을 저장하는 answer는 중복이 되는 답이 있을 수 있을 것이라고 생각했기 때문에 Set을 이용했다. 또한 check도 Set을 이용해서 이전에 탐색했던 물이 차있는 상황을 저장하며 중복을 회피했다.

 

세 번째 물통에 물이 가득 차있는 가장 첫번째 상황부터 시작했다. 첫 번째 상황도 첫 번째 물통이 비어있는 상황이기 때문에 탐색하기 전에 answer와 check에 추가해줬다. while문 내부에는 for문이 이중으로 존재하는데 외부의 for문은 선택한 물통에서 다른 물통으로 붓기 위해 물이 있는 물통을 선택하는 for문이고, 내부의 for문은 물을 부을 통을 고르기 위함이다. 

 

통에 물이 가득 차있거나, 선택한 물통이 같으면 continue 시켜주고 계산했다. 이후 계산한 값은 check에 저장되고 첫 번째 물통에 물이 있는지 없는지를 확인하고 answer에 넣어줬다. 이때 물이 차있는 상황을 전개구문(...)을 이용해서 복사했는데 for문에서 계속 사용되기 때문에 참조에 의한 원본 배열의 수정을 고려하는 이유였다.

 

queue에 더 이상 들어있는 물통의 상황이 없을 때 while 문이 종료되고 정렬하고 join을 이용해서 console.log를 한번만 사용하면서 문제를 해결했다.

 

⌨️ 코드

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./testcase/2251.txt";

const inputs = fs.readFileSync(filePath).toString().trim().split("\n");

const bottle = inputs[0].split(" ").map(Number);
const queue = [[0, 0, bottle[2]]];

const answer = new Set();
answer.add(bottle[2]);
const checkHash = new Set();
checkHash.add(queue[0].join("-"));

while (queue.length) {
  const target = queue.pop();

  for (let i = 0; i < 3; i++) {
    if (!target[i]) continue;

    for (let j = 0; j < 3; j++) {
      const water = [...target];
      if (i === j) continue;
      if (water[j] === bottle[j]) continue;

      if (water[i] <= bottle[j] - water[j]) {
        water[j] += water[i];
        water[i] = 0;
      } else {
        water[i] -= bottle[j] - water[j];
        water[j] = bottle[j];
      }

      const check = water.join("-");
      if (checkHash.has(check)) continue;

      checkHash.add(check);
      if (!water[0]) answer.add(water[2]);
      queue.push(water);
    }
  }
}

console.log([...answer.values()].sort((a, b) => a - b).join(" "));