백준 2251 물통

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

문제 설명

문제

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

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

입력

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

출력

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

---

문제 풀이

a → b, c

b → a, c

c → a, b 로 물을 옮기는 경우의 수를 전부 구하고 (단, 중복이 되는 경로는 추가가 되면 안됨)

a가 0이 되었을 경우 c의 값을 answer에 추가 최종적으로 answer을 중복제거하고 정렬하여 ‘ ‘로 이어주면 됨.

const inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let [a, b, c] = inputs[0].split(" ").map(Number);

// bfs
let answer = [];
let visited = new Set();
let check = [[0, 0, c]];

const processVisited = (tmp) => {
  const key = JSON.stringify(tmp);
  if (!visited.has(key)) {
    check.push(tmp);
    visited.add(key);
  }
};

const transfer = (state, from, to, limit) => {
  const nextState = [...state];
  const transfer_amount = Math.min(limit - nextState[to], nextState[from]);

  nextState[from] -= transfer_amount;
  nextState[to] += transfer_amount;

  processVisited(nextState);
};

const bfs = () => {
  while (check.length > 0) {
    let current = check.pop();
    // 물통이 비어있으면 C 추가
    if (current[0] === 0) {
      answer.push(current[2]);
    }

    // 물을 옮길 수 있는 경우 구하기
    // a -> b
    transfer(current, 0, 1, b);
    // a -> c
    transfer(current, 0, 2, c);
    // b -> a
    transfer(current, 1, 0, a);
    // b -> c
    transfer(current, 1, 2, c);
    // c -> a
    transfer(current, 2, 0, a);
    // c -> b
    transfer(current, 2, 1, b);
  }
};

bfs();

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

---

결론

물을 옮기는 경우의 수에 대한 로직을 if로 전부 처리하였는데 해당 로직을 transfer함수로 분리하였음

→ 코드 중복 제거 및 가독성 증가

 

[1, 2, 3] 형태를 set에 추가하여 has()를 통해 검사를 하려고 하였는데 동일한 참조(reference)가 아니면 제대로 검사가 안됨

→ 해당 부분은 JSON.stringify를 이용해 문자열로 변환하여 검사하도록 함

 

그 외 js 문법 정리 (Set, dict)

1. let a = {}의 경우

let a = {};
b = [1, 2, 3];
a.add(b); // TypeError: a.add is not a function

• a는 일반 객체(Object)입니다.
• 객체에는 add 메서드가 기본적으로 존재하지 않습니다.
• 일반 객체에서는 키-값 쌍을 정의하거나 속성을 추가하는 방식으로만 사용할 수 있습니다.

일반 객체에서 동작 예:

let a = {};
a["key"] = [1, 2, 3]; // 객체에 속성 추가
console.log(a); // { key: [1, 2, 3] }

---

2. let a = new Set()의 경우

let a = new Set();
b = [1, 2, 3];
a.add(b); // 정상 작동
console.log(a); // Set { [1, 2, 3] }

• Set은 고유한 값들을 저장하는 특수한 데이터 구조입니다.
• Set에는 add 메서드가 정의되어 있어, 값을 추가할 수 있습니다.
• 이 경우, 참조 타입(b라는 배열)은 객체의 참조를 저장합니다.

---

핵심 차이

특징	일반 객체 {}	Set
메서드 지원	add 없음	add, has, delete 지원
저장 방식	키-값 쌍(a[key] = value)	값만 저장 (고유한 값 유지)
참조 비교	직접 관리 필요 (JSON.stringify 등)	참조 기준으로 동작