[BOJ] 백준 2251번 물통 (Java)

#2251 물통

난이도 : 골드 5

유형 : 그래프 탐색 / BFS / DFS / 브루트포스 

2251번: 물통

▸ 문제

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

물통의 갯수도 3개 제한이고 부피의 총량도 최대 200이라 그렇게 구현하기 어려운 문제는 아니다. 다만 자바의 입장에서는 다소 까다로울 수도 있다. 각 케이스 별로 클래스 객체를 만들어 다른 과정과 간섭받지 않도록 설계해줘야 한다. 배열 값들이 모든 연산과정에서 변경되기 때문에 따로 깊은 복사 배열을 만들어서 매 케이스마다 다뤄주는 방법은 안된다. 배열은 주소값을 참조하더라도 값이 변경되기 때문에 탐색에서 각 배열의 관계를 독립시키기가 어렵다.

 

• DFS 풀이에서는 위의 두 데이터 분배 과정보다는 차라리 재귀 함수 인자 값에 각 용량을 담아서 탐색하는 것이 훨씬 수월하다.
• BFS 풀이에서는 위의 두 데이터 분배 과정을 적용하는데 세 개의 물통의 담긴 용량을 담는 배열을 가지는 클래스를 구현하여 모든 케이스마다 새로운 클래스 객체를 생성해주면 된다.
• DFS는 가시성과 빠른 구현을 할 수 있다는 장점이 있지만 BFS는 다소 구현과정이 더 길더라도 재귀호출 스택보다는 메모리 사용량에서 더 우월하다.

 

공통 로직

풀이하는 로직은 같다. 모든 과정은 from → to로 물통에 있는 물이 이동하는데 케이스는 2가지로 나뉜다.

1. from + to에 담긴 물의 양이 to의 전체 용량보다 클 경우, 그러면 from에 있는 모든 양을 옮길 수 없기 때문에 부분만 이동한다.
   1. bucket[from] -= limit[to] -tmp[to]; // from에 있는 물의 양을 (to전체용량 - to에 담긴 물의 양)만큼 옮긴다.
   2. bukcet[to] = limit[to];  // to에는 물이 꽉차게 된다.
2. 그 외의 경우, from에 있는 모든 물의 양을 to로 옮겨주면 된다.
   1. bucket[to] = bucket[from] + bucekt[to]; // to에 from에 있는 물의 양을 전부 옮겨준다.
   2. bukcet[from] = 0; // from의 물통은 비게 된다.
3. 해당 탐색을 이어가면서 1번 물통이 비게 될 경우, 3번 물통의 양을 저장해주면 된다.

그리고 방문여부는 1번 2번의 물의 양으로 체크해주면 된다. 3번 물의 양은 Set자료구조로 따로 해주기 있기 때문에 크게 상관없고 1,2번에 담긴 물의 양에 따라 3번 물의 양이 자동으로 정해지기 때문이다.

 

풀이 코드 

DFS 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	static int[] limit;
	static boolean[][] check;
	static Set<Integer> answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		limit = new int[3];
		check = new boolean[201][201];
		for(int i=0; i<3; i++) {
			limit[i] = Integer.parseInt(st.nextToken());
		}
		
		answer = new TreeSet<>();
		dfs(0,0, limit[2]);
		
		for(int num : answer) {
			System.out.print(num+" ");
		}
	}
	static void dfs(int a, int b, int c){
		if(check[a][b]) return;
		
		if(a==0) {
			answer.add(c);
		}
		check[a][b] = true;
		// 0 -> 1
		if(a+b > limit[1]) {
			dfs((a+b)-limit[1], limit[1], c);
		}else {
			dfs(0, a+b, c);
		}
		
		// 1 -> 0
		if(a+b > limit[0]) {
			dfs(limit[0], a+b-limit[0], c);
		}else {
			dfs(a+b, 0, c);
		}
		
		// 2 -> 0
		if(a+c > limit[0]) {
			dfs(limit[0], b, a+c-limit[0]);
		}else {
			dfs(a+c, b, 0);
		}
		
		
		// 2 -> 1
		if(b+c > limit[1]) 	{
			dfs(a, limit[1], b+c-limit[1]);
		}else {
			dfs(a, b+c, 0);
		}
		
		// 0 -> 2
		dfs(a, 0, b+c);
		// 1 -> 2
		dfs(0, b, a+c);
	}
}

 

BFS 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	static class Bucket{
		int[] tmp;
		public Bucket(int[] tmp) {
			this.tmp = new int[3];
			for(int i=0; i<3; i++) {
				this.tmp[i] = tmp[i];
			}
		}
		
		Bucket move(int from, int to) {
			int[] ttmp = {tmp[0], tmp[1], tmp[2]};
			if(tmp[from] + tmp[to] > limit[to]) {
				ttmp[from] -= limit[to]-tmp[to];
				ttmp[to] = limit[to];
			}else{
				ttmp[from] = 0;
				ttmp[to] = tmp[from] + tmp[to];
			}
			return new Bucket(ttmp);
		}
		
	}
	static int[] limit, bucket;
	static boolean[][] check;
	static Set<Integer> answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		limit = new int[3];
		bucket = new int[3];
		for(int i=0; i<3; i++) {
			limit[i] = Integer.parseInt(st.nextToken());
		}
		
		answer = new TreeSet<>();
		bfs();
		
		for(int num : answer) {
			System.out.print(num+" ");
		}
	}
	static void bfs(){
		Queue<Bucket> q= new LinkedList<>();
		q.add(new Bucket(new int[] {0,0,limit[2]}));
		check = new boolean[201][201];
		check[0][0] = true;
		while(!q.isEmpty()) {
			Bucket p = q.poll();
			if(p.tmp[0]==0) {
				answer.add(p.tmp[2]);
			}
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					if(i!=j) {
						Bucket nxt = p.move(i,j);
						if(!check[nxt.tmp[0]][nxt.tmp[1]]) {
							check[nxt.tmp[0]][nxt.tmp[1]] = true;
							q.add(nxt);
						}
					}
				}
			}
		}
	}
}