2251

 

물통 : https://www.acmicpc.net/problem/2251

 

 

BFS

1. 비효율적이긴 하지만 ArraysCopyOf 함수를 활용해보고 싶었다.

2. 이전 퍼즐문제에서 사용했던, HashMap 및 String을 조합하여 중복을 체크하였다.

String.format을 사용해 a,b,c 현재 물의 양을 Key값으로 함.

 

3. 숏코드에서 확인한 바와 같이 2차원 배열을 활용하여 중복을 체크하는 것이 성능상 더 나은 선택이 되겠다.

(전체 물의 양이 정해져 있으므로 A,B 값을 체크하면 C의 값은 확인할 필요가 없다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static boolean DBG = false;
	static HashMap<String, Integer> dup;
	static HashSet<Integer> answer;
	static int[] arr;
	static int[] init;

	static int A = 0;
	static int B = 1;
	static int C = 2;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[3];
		init = new int[3];
		dup = new HashMap<>();
		answer= new HashSet<>();
		// 0 size , 1 water
		for (int t = 0; t < 3; t++) {
			arr[t] = Integer.parseInt(st.nextToken());
		}

		// init only 3rd has water
		init[C] = arr[C];
		bfs();
		
		ArrayList<Integer> ar = new ArrayList<>(answer);
		Collections.sort(ar);
		for ( int v : ar)
			System.out.print(v + " ");

	}

	private static int bfs() {
		Queue<int[]> Q = new LinkedList<>();

		// 초기 A의 물은 없으므로 현재 물의 양을 저장
		String initKey = String.format("%d%d%d", init[A], init[B], init[C]);
		dup.put(initKey, init[C]);
		answer.add(init[C]);
		
		Q.offer(Arrays.copyOf(init, init.length));

		while (!Q.isEmpty()) {
			int size = Q.size();
			int level = 0;
			for (int q = 0; q < size; ++q) {
				int[] water = Q.poll();
				deliverWater(A, B, Arrays.copyOf(water, water.length), Q);
				deliverWater(A, C, Arrays.copyOf(water, water.length), Q);
				deliverWater(B, A, Arrays.copyOf(water, water.length), Q);
				deliverWater(B, C, Arrays.copyOf(water, water.length), Q);
				deliverWater(C, A, Arrays.copyOf(water, water.length), Q);
				deliverWater(C, B, Arrays.copyOf(water, water.length), Q);
				
			}
			level++;
		}
		return -1;
	}

	static void deliverWater(int src, int dst, int [] water , Queue<int[]> Q){
		if (water[src] != 0) {
			//src to dst
			int empty = (arr[dst] - water[dst]);//빈공간
			int capacity = (water[src] > empty)? empty: water[src]; //A물을 얼마나 빈공간에 넣을 수 있는가?
			
			water[src] -= capacity;
			water[dst] += capacity;

			String tmp = String.format("%d%d%d", water[A], water[B], water[C]);
			if( DBG )
			System.out.println(tmp);
			if (!dup.containsKey(tmp)) {
				dup.put(tmp, water[C]);
				
				//A가 0일 경우만 C의 물의 양이 정답에 추가됨.
				if (water[A] == 0)
					answer.add(water[C]);						
				Q.offer(Arrays.copyOf(water, water.length));
			}
		}
	}
	
}









//숏코드 참조하여 개선한 버전
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	static boolean DBG = false;
	static boolean[][] dup;
	static TreeSet<Integer> answer;
	static int[] arr;
	static int[] init;

	static int A = 0;
	static int B = 1;
	static int C = 2;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[3];
		init = new int[3];
		dup = new boolean[201][201];
		answer = new TreeSet<>();
		// 0 size , 1 water
		for (int t = 0; t < 3; t++) {
			arr[t] = Integer.parseInt(st.nextToken());
		}
		// init only 3rd has water
		init[C] = arr[C];
		bfs();

		ArrayList<Integer> ar = new ArrayList<>(answer);
		for (int v : ar)
			System.out.print(v + " ");

	}

	private static int bfs() {
		Queue<int[]> Q = new LinkedList<>();

		// 초기 A의 물은 없으므로 현재 물의 양을 저장
		dup[init[A]][init[B]] = true;
		answer.add(init[C]);

		Q.offer(Arrays.copyOf(init, init.length));

		while (!Q.isEmpty()) {
			int size = Q.size();
			for (int q = 0; q < size; ++q) {
				int[] water = Q.poll();
				// A가 0일 경우만 C의 물의 양이 정답에 추가됨.
				if (water[A] == 0)
					answer.add(water[C]);

				deliverWater(A, B, Arrays.copyOf(water, water.length), Q);
				deliverWater(A, C, Arrays.copyOf(water, water.length), Q);
				deliverWater(B, A, Arrays.copyOf(water, water.length), Q);
				deliverWater(B, C, Arrays.copyOf(water, water.length), Q);
				deliverWater(C, A, Arrays.copyOf(water, water.length), Q);
				deliverWater(C, B, Arrays.copyOf(water, water.length), Q);
			}
		}
		return -1;
	}

	static void deliverWater(int src, int dst, int[] water, Queue<int[]> Q) {

		int empty = (arr[dst] - water[dst]);// 빈공간
		int capacity = (water[src] > empty) ? empty : water[src];

		water[src] -= capacity;
		water[dst] += capacity;

		if (DBG)
			System.out.printf("%d%d%d\n", water[A], water[B], water[C]);

		if (!dup[water[A]][water[B]]) {
			dup[water[A]][water[B]] = true;
			Q.offer(Arrays.copyOf(water, water.length));
		}
	}

}

 

 

 

DFS 

 

DFS 참조

1.https://www.acmicpc.net/source/11839520

2.https://loosie.tistory.com/513

 

생각하지 못한점.

1. TreeSet을 사용하면 정렬을 해줄 필요가 없다.

2. 중복체크는 a,b의 값을 좌표로한 2by2 배열로 가능하다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	static boolean DBG = false;
	static boolean[][] dup;
	static TreeSet<Integer> answer;

	// size of bucket
	static int A;
	static int B;
	static int C;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		dup = new boolean[201][201];
		answer = new TreeSet<>();

		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		dfs(0, 0, C);

		ArrayList<Integer> ar = new ArrayList<>(answer);		
		for (int v : ar)
			System.out.print(v + " ");

	}

	private static void dfs(int a, int b, int c) {

		if (dup[a][b])
			return;

		if (a == 0) {
			answer.add(c);
		}

		dup[a][b] = true;

		// A->B
		if (a + b > B)
			dfs(a + b - B, B, c);
		else
			dfs(0, a + b, c);

		// A->C
		if (a + c > C)
			dfs(a + c - C, b, C);
		else
			dfs(0, b, a + c);

		// B->A
		if (a + b > A)
			dfs(A, a + b - A, c);
		else
			dfs(a + b, 0, c);
		// B->C
		if (b + c > C)
			dfs(a, b + c - C, C);
		else
			dfs(a, 0, b + c);
		// C->A
		if (a + c > A)
			dfs(A, b, a + c - A);
		else
			dfs(a + c, b, 0);
		// C->B
		if (b + c > B)
			dfs(a, B, b + c - B);
		else
			dfs(a, b + c, 0);

	}

}