[Baekjoon] 2251_물통

Gold V

문제(출처: https://www.acmicpc.net/problem/2251)

---

< 물통 >

 

문제 풀이 

 

물통을 A->B, A->C, B->A, B->C, C->A, C->B로 이동하는 경우를 구한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _2251_ { // 물통

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		Queue<int[]> queue = new LinkedList<>();
		ArrayList<Integer> list = new ArrayList<>();
		boolean visited[][][] = new boolean[a + 1][b + 1][c + 1];

		queue.add(new int[] { 0, 0, c });
		list.add(c);
		visited[0][0][c] = true;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();

			if (temp[0] == 0 && !list.contains(temp[2])) {
				list.add(temp[2]);
			}

			if (temp[0] > 0) {
				// a->b
				if (temp[1] + temp[0] < b) {
					if (!visited[0][temp[1] + temp[0]][temp[2]]) {
						visited[0][temp[1] + temp[0]][temp[2]] = true;
						queue.add(new int[] { 0, temp[1] + temp[0], temp[2] });
					}
				} else {
					if (!visited[temp[0] - (b - temp[1])][b][temp[2]]) {
						visited[temp[0] - (b - temp[1])][b][temp[2]] = true;
						queue.add(new int[] { temp[0] - (b - temp[1]), b, temp[2] });
					}
				}

				// a->c
				if (temp[2] + temp[0] < c) {
					if (!visited[0][temp[1]][temp[2] + temp[0]]) {
						visited[0][temp[1]][temp[2] + temp[0]] = true;
						queue.add(new int[] { 0, temp[1], temp[2] + temp[0] });
					}
				} else {
					if (!visited[temp[0] - (c - temp[2])][temp[1]][c]) {
						visited[temp[0] - (c - temp[2])][temp[1]][c] = true;
						queue.add(new int[] { temp[0] - (c - temp[2]), temp[1], c });
					}
				}
			}

			if (temp[1] > 0) {
				// b->a
				if (temp[0] + temp[1] < a) {
					if (!visited[temp[0] + temp[1]][0][temp[2]]) {
						visited[temp[0] + temp[1]][0][temp[2]] = true;
						queue.add(new int[] { temp[1] + temp[0], 0, temp[2] });
					}
				} else {
					if (!visited[a][temp[1] - (a - temp[0])][temp[2]]) {
						visited[a][temp[1] - (a - temp[0])][temp[2]] = true;
						queue.add(new int[] { a, temp[1] - (a - temp[0]), temp[2] });
					}
				}

				// b->c
				if (temp[2] + temp[1] < c) {
					if (!visited[temp[0]][0][temp[2] + temp[1]]) {
						visited[temp[0]][0][temp[2] + temp[1]] = true;
						queue.add(new int[] { temp[0], 0, temp[2] + temp[1] });
					}
				} else {
					if (!visited[temp[0]][temp[1] - (c - temp[2])][c]) {
						visited[temp[0]][temp[1] - (c - temp[2])][c] = true;
						queue.add(new int[] { temp[0], temp[1] - (c - temp[2]), c });
					}
				}
			}

			if (temp[2] > 0) {
				// c->a
				if (temp[0] + temp[2] < a) {
					if (!visited[temp[0] + temp[2]][temp[1]][0]) {
						visited[temp[0] + temp[2]][temp[1]][0] = true;
						queue.add(new int[] { temp[2] + temp[0], temp[1], 0 });
					}
				} else {
					if (!visited[a][temp[1]][temp[2] - (a - temp[0])]) {
						visited[a][temp[1]][temp[2] - (a - temp[0])] = true;
						queue.add(new int[] { a, temp[1], temp[2] - (a - temp[0]) });
					}
				}

				// c->b
				if (temp[2] + temp[1] < b) {
					if (!visited[temp[0]][temp[1] + temp[2]][0]) {
						visited[temp[0]][temp[1] + temp[2]][0] = true;
						queue.add(new int[] { temp[0], temp[1] + temp[2], 0 });
					}
				} else {
					if (!visited[temp[0]][b][temp[2] - (b - temp[1])]) {
						visited[temp[0]][b][temp[2] - (b - temp[1])] = true;
						queue.add(new int[] { temp[0], b, temp[2] - (b - temp[1]) });
					}
				}
			}
		}
		Collections.sort(list);
		for (int x : list) {
			bw.write(x + " ");
		}
		bw.flush();
	}
}

변수)
a, b, c : 세 개의 물통 부피
queue : Queue <int [각 물통에 들어있는 물의 양]>
list : C에 담겨있을 수 있는 물의 양
visited : 방문 여부

 

A, B, C를 입력받는다. Queue에 초기 물통의 값인 [0,0, c]를 저장한다. list에도 c를 저장하고 [0,0, c]를 방문처리한다. Queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue에서 값을 poll 한다.

2) a 물통이 비어있고 list에 없는 값이라면 c물통에 있는 물의 양을 list에 추가한다.

3) a 물통에 물이 있다면 a -> b, a -> c로 물을 이동한다. 이때, 이동하려는 물통에 있던 원래 물의 양과 이동하려는 물의 양의 합이 그 물통에 넘치는지 넘치지 않는지 확인한다. 넘치지 않는다면 이동한다. 넘친다면 이동할 수 있는 물의 양만 이동한다.

4) b 물통에 물이 있다면 b -> a, b -> c로 물을 이동한다.

5) c 물통에 물이 있다면 c -> a, c -> b로 물을 이동한다.

 

list를 오름차순으로 정렬 후 출력한다.

---

 

---