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

Key Point

처음에 a,b는 비어있고, c만 가득 채워져있는 상태이므로 c의 용량은
c = C - a - b로 계산할 수 있다.
a의 용량 > b의 용량일 경우, a->b로 물을 부었을 경우
넘친 만큼을 a로 다시 부어주는 상황을 생각해야 한다.

Explain

각 물통의 용량을 입력으로 받는다. 그리고 처음에 앞에 두 물통은 비어있고, C만 가득차있다.
물을 옮기는 과정에서 손실되는 물이 없는 것이 중요한 점이다.
이 때, 첫 번쨰 물통 A가 비어있을 때, 세 번째 물통 C에 담겨 있을 수 있는 물의 양을 모두 구하는 것이다.
[오름차순] BFS를 이용해서 문제를 푼다.

Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Pair implements Comparable<Pair>{
int first; // 첫번째 물통
int second; // 두번째 물통

Pair(int first,int second){
this.first = first;
this.second = second;
}

@Override
public int compareTo(Pair pair) {
if(this.first<pair.first) {
return -1;
}

if(this.first>pair.first) {
return 1;
}

if(this.second<pair.second) {
return -1;
}

if(this.second>pair.second) {
return 1;
}

return 0;
}
}

public class Exam2251 {

public static final int[] from = {0,0,1,1,2,2};
public static final int[] to = {1,2,0,2,0,1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] cap = new int[3];
for(int i=0;i<3;i++) {
cap[i] = sc.nextInt();
}
int sun = cap[2]; // a+b+c = C
boolean[][] check = new boolean[201][201];
boolean[] ans = new boolean[201];
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(0,0));
check[0][0] = true;
ans[cap[2]] = true;

while(!q.isEmpty()) {
int[] current = new int[3];
Pair p = q.peek();
current[0] = p.first;
current[1] = p.second;
current[2] = sun - current[0] - current[1];
q.remove();
for(int i=0;i<6;i++) {
int[] next = {current[0],current[1],current[2]};
next[to[i]] +=next[from[i]]; // 물통에 있는 물 따르기 ex) a->b
next[from[i]] = 0; // 물통비우기

if(next[to[i]]>=cap[to[i]]) {
next[from[i]] = next[to[i]] - cap[to[i]];
next[to[i]] = cap[to[i]];
}

// q에 없던 친구들이라면!
// 즉, check[next[0]][next[1]]이 false라면
if(!check[next[0]][next[1]]) {
check[next[0]][next[1]] = true;
q.add(new Pair(next[0],next[1]));
if(next[0] == 0) {
ans[next[2]] = true;
}
}
}
}
for(int k=0;k<=cap[2];k++) {
if(ans[k] == true) {
System.out.print(k+" ");
}
}


}

}