JUST WRITE IT. HomeArchivesTagsCategories
백준 2251번 물통
|AlgorithmBOJ|

#2251. 물통

Problem

Solution

  • 첫 시작은 C 물통만 가득 차 있으니 전체 합은 C의 물통이다.
  • 물을 옮기는 경우는 총 6경우로 0을 A, 1을 B, 2를 C라고 했을 때 다음과 같은 경우가 존재한다.
    1
    2
    3
    0 -> 1, 0 -> 2
    1 -> 0, 1 -> 2
    2 -> 0, 2 -> 1
  • 경우의 수가 중복되지 않도록 표시해주는 배열은 2차원으로도 해결 가능하다. (전체 양은 일정하니 A, B만 알아도 C를 알 수 있기 때문이다.)
  1. 처음 A, B, C의 부피를 저장한다.
  2. 시작은 (0, 0)에서 시작하고, ans[C 물의 양]이 true임을 표시해 A가 0일 때 C의 물의양임을 나타낸다.
  3. BFS 탐색을 시작한다. 각 경우에서 계속해서 나아가는 방식이기에 적합하다. (경우의 수도 많지 않음)

  4. 물을 옮기는 건 2가지 경우가 존재한다.

    from x → to y

    1. x + y ≤ Y
      x + y의 값이 y를 가진 물통의 부피(Y)이하일 때
      x를 다 옮길 수 있으므로 x를 가졌던 물통의 물의 양은 0이 된다.
      y를 가진 물통의 물의 양은 x+y가 된다.
    2. x + y > Y
      x + y의 값이 Y보다 클 때 x를 다 옮길 수 없으므로
      x를 가졌던 물통의 물의 양은 x + y - Y가된다.
      y를 가졌던 물통의 물의 양은 Y가 된다.
    1. check와 A의 물의 양이 0인지 판단하여 BFS 탐색을 한다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <queue>
using namespace std;
int bucket[3]; // 물통 부피
bool check[201][201]; // A, B만 알아도 C를 알 수 있음
bool ans[201]; // A가 비어있을 때 C의 물의 양
queue<pair<int, int>> q;
int from[6] = { 0, 0, 1, 1, 2, 2 }; // 0: A, 1: B, 2: C
int to[6] = { 1, 2, 0, 2, 0, 1 };
void Output() {
	for (int i = 0; i <= 200; ++i) {
		if (ans[i]) cout << i << " ";
	}
	cout << "\n";
}
void BFS() {
	int sum = bucket[2];
	q.push({ 0, 0 });
	check[0][0]= true;
	ans[sum] = true;
	while (!q.empty()) {
		int cur[3];
		cur[0] = q.front().first;
		cur[1] = q.front().second;
		cur[2] = sum - cur[0] - cur[1];
		q.pop(); 
		for (int i = 0; i < 6; ++i) {
			int next[3] = { cur[0], cur[1], cur[2] };
			if (next[from[i]] + next[to[i]] <= bucket[to[i]]) { 
				next[to[i]] += next[from[i]];
				next[from[i]] = 0;
			}
			else { // 옮긴 물의 양이 해당 물통 부피보다 클 때
				next[from[i]] += next[to[i]] - bucket[to[i]];
				next[to[i]] = bucket[to[i]];
			}
			if (!check[next[0]][next[1]]) {
				check[next[0]][next[1]] = true;
				q.push({ next[0], next[1] });
				if (next[0] == 0) ans[next[2]] = true;
			}
		}
	}	
}
int main() {
	for (int i = 0; i < 3; ++i) cin >> bucket[i];
	BFS();
	Output();
	return 0;
}
Algorithm