문제 : 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+" ");
			}
		}
		
		
	}

}