Algorithm, boj, 물통(2251)

물통

풀이

1. A , B , C 물통이 있을때 물이 담겨있는 한가지 상황에 대해
여섯가지 방법으로 물을 따라서 상황을 바꿀수있다.
A -> B
A -> C
B -> A
B -> C
C -> A
C -> B

2. 새로 생겨난 상황이 이전에도 있었는지 HashSet을 이용해서 확인하고

3. 처음 보는 상황이라면 Queue에 넣어
다시 6가지 방법으로 따라본다.

4. Queue가 빌때까지 반복한다.

핵심

• 한가지 상황에 대해서 상황이 어떻게 바뀔수 있는지를 알아야 한다.
• 바뀐 상황이 새로운 상황이면 큐에 삽입

코드

package org.baekjoon;

import java.util.*;

public class test2251_waterBottle {
	static int a, b, c;
	static Queue<int[]> q;
	static HashSet<String> hs;
	static int[] origin;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		origin = new int[3];
		for (int i = 0; i < 3; i++) {
			origin[i] = sc.nextInt();
		}

		q = new LinkedList<>();
		hs = new HashSet<>();
		int[] first = {0,0,origin[2]};
		q.offer(first);

		bfs();

	}

	private static void bfs() {
		List<Integer> list = new ArrayList<>();
		while (!q.isEmpty()) {
			int[] bottle = q.poll();
			if (bottle[0] == 0)
				list.add(bottle[2]);

			for (int give = 0; give < 3; give++) {
				for (int j = 1; j < 3; j++) {
					int[] newBottle = bottle.clone();
					int receive = (give + j) % 3;
					// 줄수없으면 변화가 없으므로 패쓰.
					// 줄수있는게 0 ㅇ이거나 받을수있는게 0
					if (bottle[give] == 0 || bottle[receive] == origin[receive])
						continue;

					if (bottle[give]+bottle[receive] > origin[receive]) {
						newBottle[give] = bottle[give] - (origin[receive]-newBottle[receive]);
						newBottle[receive] = origin[receive];
					}else {
						newBottle[receive] += bottle[give];
						newBottle[give] = 0;
					}

					String str = "";
					for(Integer b : newBottle) {
						str += b;
					}
					if(!hs.contains(str)) {
						q.offer(newBottle);
						hs.add(str);
					}

				}
			}

		}

		Collections.sort(list);
		for(int i=0; i<list.size()-1; i++)
			System.out.print(list.get(i)+" ");

	}

}

비슷한 문제 - 돌그룹(12886)