물통

문제

백준 2251번 - 물통

언어

JavaScript

순서도

BFS 탐색

문제 풀이 step 1

각 부피가 A, B, C 리터인 세 개의 물통이 있습니다.
처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득 (C 리터) 차 있습니다.
이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있습니다.
- 이 과정에서 손실되는 물은 없다고 가정합니다.
이와 같은 과정을 거치다보면 세 번째 물통 (용량이 C 인) 에 담겨있는 물의 양이 변할 수도 있습니다.
첫 번재 물통 (용량이 A 인) 이 비어 있을 때, 세 번째 물통 (용량이 C 인) 에 담겨있을 수 있는 물의 양을 모두 구해내는 문제입니다.

문제 풀이 step 2

우선 A, B, C 각 물통마다 방문 처리를 할 수 있도록 크기가 200 인 3 차원 배열을 생성합니다.
BFS 탐색을 진행합니다.
- 탐색은 총 6 가지 경우로 이루어집니다.
  - A 물통에서 B 물통으로 물을 붓는 경우
  - A 물통에서 C 물통으로 물을 붓는 경우
  - B 물통에서 A 물통으로 물을 붓는 경우
  - B 물통에서 C 물통으로 물을 붓는 경우
  - C 물통에서 A 물통으로 물을 붓는 경우
  - C 물통에서 B 물통으로 물을 붓는 경우
- 물을 부을 때, “한 물통이 비거나, 다른 한 물통이 가득 찰 때까지” 이 말에 유의해서 구현합니다.
- 그리고 위에서 만들었던 3 차원 배열을 이용해서 방문 처리를 해가며 탐색을 합니다.
- 탐색 도중에 A 물통이 0 리터인 경우, C 물통의 물의 양을 기록합니다.
마지막으로 가능한 모든 C 물통의 물의 양을 오름 차순으로 정렬 후 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

기업 코딩테스트에서 이와 비슷한 문제가 나왔지만 못 풀어서 아쉬웠는데, 위 문제 덕분에 공부할 수 있게 되어서 행운입니다.
문제를 접할 때 실제 그래프나 2 차원 배열을 탐색하는 경우에만 BFS 탐색이라는 방법을 생각했었는데, 위 문제를 풀고 나서 조금 생각의 틀을 넓힐 수 있었습니다.
- 탐색할 때에도 탐색 방향이 주어지는 것이 아니라, 탐색 경우의 수를 고려해서 그에 맞게 탐색을 한다는 것도 기존의 문제와 조금 달랐던 점이었습니다.
그리고 저는 3 차원 배열을 사용해서 풀었지만, SET 을 이용해서 풀면 공간 복잡도와 시간 복잡도를 크게 줄일 수 있습니다.
그리고 저는 BFS 탐색을 할 때, 방문 처리를 하고 탐색을 하는데, 탐색을 하고 방문 처리를 할 수도 있다는 것을 깨달았습니다. (개인적인 깨달음)

소스 코드

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

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

const BFS = (
	aLimit,
	bLimit,
	cLimit,
	aWater,
	bWater,
	cWater,
	visited,
	cCase
) => {
	const queue = new Queue();
	visited[aWater][bWater][cWater] = true;
	queue.enqueue([aWater, bWater, cWater]);

	while (!queue.isEmpty()) {
		let [aBase, bBase, cBase] = queue.dequeue();

		const cases = [];
		// A 물통
		if (aBase !== 0) {
			// A -> B
			if (bLimit - bBase > aBase) cases.push([0, bBase + aBase, cBase]);
			else
				cases.push([aBase - (bLimit - bBase), bBase + (bLimit - bBase), cBase]);
			// A -> C
			if (cLimit - cBase > aBase) cases.push([0, bBase, cBase + aBase]);
			else
				cases.push([aBase - (cLimit - cBase), bBase, cBase + (cLimit - cBase)]);
		}

		// B 물통
		if (bBase !== 0) {
			// B -> A
			if (aLimit - aBase > bBase) cases.push([aBase + bBase, 0, cBase]);
			else
				cases.push([aBase + (aLimit - aBase), bBase - (aLimit - aBase), cBase]);
			// B -> C
			if (cLimit - cBase > bBase) cases.push([aBase, 0, cBase + bBase]);
			else
				cases.push([aBase, bBase - (cLimit - cBase), cBase + (cLimit - cBase)]);
		}

		// C 물통
		if (cBase !== 0) {
			// C -> A
			if (aLimit - aBase > cBase) cases.push([aBase + cBase, bBase, 0]);
			else
				cases.push([aBase + (aLimit - aBase), bBase, cBase - (aLimit - aBase)]);
			// C -> B
			if (bLimit - bBase > cBase) cases.push([aBase, bBase + cBase, 0]);
			else
				cases.push([aBase, bBase + (bLimit - bBase), cBase - (bLimit - bBase)]);
		}

		// 가능한 모든 경우 중에서 방문 처리 후, 탐색 진행
		for (let i = 0; i < cases.length; i++) {
			const [aWater, bWater, cWater] = cases[i];

			if (visited[aWater][bWater][cWater]) continue;

			// A 물통이 비어있다면, C 물통의 양 기록
			if (aWater === 0) cCase[cWater] = true;
			visited[aWater][bWater][cWater] = true;
			queue.enqueue([aWater, bWater, cWater]);
		}
	}
};

const solution = (input) => {
	const [aLimit, bLimit, cLimit] = input[0].split(" ").map(Number);
	let [aWater, bWater, cWater] = [0, 0, cLimit];

	// 방문 처리를 위해서 3 차원 배열 생성
	const visited = Array.from({length: 201}, () =>
		Array.from({length: 201}, () => Array(201).fill(false))
	);

	const cCase = Array(201).fill(false);
	cCase[cWater] = true;
	BFS(aLimit, bLimit, cLimit, aWater, bWater, cWater, visited, cCase);

	// 가능한 C 물통의 경우 모두 출력
	const res = [];
	for (let i = 0; i < cWater + 1; i++) {
		if (cCase[i] === true) res.push(i);
	}

	return res.join(" ");
};

console.log(solution(input));