[백준] 2251. 물통 (JAVA)

🧺 물통

 

"첫 번째 물통이 비어있을 때"라는 조건을 못 보고 한참을 헤맸다. 😓

구현 자체는 어렵지 않았으나 중복 코드를 어떻게 해결할 지 아직 생각하지 못했다. . (안했다)

리팩토링.. 다음에.. 꼭..

 

---

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

 

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

 

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

 

---

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Status {
	int a;
	int b;
	int c;

	Status(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}
}

class Main {
	static Status capacity;
	static Queue<Status> queue;
	static boolean[][][] visited;
	static boolean[] cwater;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] capa = new int[3];

		for(int i=0; i<3; i++)
			capa[i] = Integer.parseInt(st.nextToken());

		capacity = new Status(capa[0], capa[1], capa[2]);

		bfs();

		for(int i=0; i<capacity.c+1; i++) {
			if(cwater[i])
				System.out.print(i + " ");
		}
	}

	private static void bfs() {
		queue = new LinkedList<>();
		visited = new boolean[capacity.a+1][capacity.b+1][capacity.c+1];
		cwater = new boolean[capacity.c+1];

		queue.offer(new Status(0, 0, capacity.c));
		visited[0][0][capacity.c] = true;

		while(!queue.isEmpty()) {
			Status status = queue.poll();
			if(status.a == 0)
				cwater[status.c] = true;
			offerQueue(status);
		}
	}

	private static void offerQueue(Status status) {
		int aSparse = capacity.a - status.a;
		int bSparse = capacity.b - status.b;
		int cSparse = capacity.c - status.c;

		if(status.a <= bSparse) {
			if(!visited[0][status.a+status.b][status.c]) {
				visited[0][status.a+status.b][status.c] = true;
				queue.offer(new Status(0, status.a+status.b, status.c));
			}
		}
		else {
			if(!visited[status.a-bSparse][capacity.b][status.c]) {
				visited[status.a-bSparse][capacity.b][status.c] = true;
				queue.offer(new Status(status.a-bSparse, capacity.b, status.c));
			}
		}

		if(status.a <= cSparse) {
			if(!visited[0][status.b][status.a+status.c]) {
				visited[0][status.b][status.a+status.c] = true;
				queue.offer(new Status(0, status.b, status.a+status.c));
			}
		}
		else {
			if(!visited[status.a-cSparse][status.b][capacity.c]) {
				visited[status.a-cSparse][status.b][capacity.c] = true;
				queue.offer(new Status(status.a-cSparse, status.b, capacity.c));
			}
		}

		if(status.b <= aSparse) {
			if(!visited[status.a+status.b][0][status.c]) {
				visited[status.a+status.b][0][status.c] = true;
				queue.offer(new Status(status.a+status.b, 0, status.c));
			}
		}
		else {
			if(!visited[capacity.a][status.b-aSparse][status.c]) {
				visited[capacity.a][status.b-aSparse][status.c] = true;
				queue.offer(new Status(capacity.a, status.b-aSparse, status.c));
			}
		}

		if(status.b <= cSparse) {
			if(!visited[status.a][0][status.b+status.c]) {
				visited[status.a][0][status.b+status.c] = true;
				queue.offer(new Status(status.a, 0, status.b+status.c));
			}
		}
		else {
			if(!visited[status.a][status.b-cSparse][capacity.c]) {
				visited[status.a][status.b-cSparse][capacity.c] = true;
				queue.offer(new Status(status.a, status.b-cSparse, capacity.c));
			}
		}

		if(status.c <= aSparse) {
			if(!visited[status.a+status.c][status.b][0]) {
				visited[status.a+status.c][status.b][0] = true;
				queue.offer(new Status(status.a+status.c, status.b, 0));
			}
		}
		else {
			if(!visited[capacity.a][status.b][status.c-aSparse]) {
				visited[capacity.a][status.b][status.c-aSparse] = true;
				queue.offer(new Status(capacity.a, status.b, status.c-aSparse));
			}
		}

		if(status.c <= bSparse) {
			if(!visited[status.a][status.b+status.c][0]) {
				visited[status.a][status.b+status.c][0] = true;
				queue.offer(new Status(status.a, status.b+status.c, 0));
			}
		}
		else {
			if(!visited[status.a][capacity.b][status.c-bSparse]) {
				visited[status.a][capacity.b][status.c-bSparse] = true;
				queue.offer(new Status(status.a, capacity.b, status.c-bSparse));
			}
		}
	}
}

BFS를 이용하여 풀이하였다. 

 

물통이 A, B, C 세 개이므로 queue를 poll할 때 마다

• A에서 B로
• A에서 C로
• B에서 A로
• B에서 C로
• C에서 A로
• C에서 B로

옮기는 경우를 모두 고려해주면 된다. 

 

💾 공간복잡도

A, B, C 각각의 최대 부피가 200이기 때문에, 

3차원 boolean형 배열 visited의 최대 크기는 200 * 200 * 200 Byte가 된다. 

즉 8,000,000B = 8MB 이므로 메모리 제한 128MB에 걸리지 않는다.

 

 

---

 

2251번: 물통