[ BOJ 2251 ] 물통 (Java)

문제

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

이 문제만 두시간 풀었다. 감 다 잃었다리
자바 넘 어렵다

문제 풀이

Queue를 이용해서 문제를 풀었다.

A, B, C 물통에 담겨있는 물의 양을 배열에 담아 Queue에 넣고, 옮길 수 있는지 체크해주었다.

1. from 물통에서 to 물통으로 물을 옮길 수 있으면 옮긴다

2. 만약 from 물통이 빌 때까지 물을 옮길 수 있다면
   from 물통의 양은 0, to 물통의 양은 from + to

3. from 물통이 비기 전에 to 물통이 꽉 차면
   to 물통의 양은 to 최대량, from 물통의 양은 from - (to 최대량 - to)

• 중복 체크
  A, B, C 물통에 담겼었던 물의 양을 list 배열에 담고,
  같은 물의 양은 체크하지 않도록 해주었다.
• 정답 체크
  A 물통 물의 양이 0일 때, C 물통의 양을 ans 배열에 담고,
  같은 물의 양은 담기지 않도록 해주었다.

코드

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

public class BOJ_2251_물통 {
	public static Queue<int[]> q;
	public static int[] nums;
	public static ArrayList<int[]> list;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer> ans = new ArrayList<>();
		list = new ArrayList<>();
		nums = new int[] {a, b, c};
		int[] start = {0, 0, c};
		
		q = new LinkedList<>();
		q.offer(start);
		
		while (!q.isEmpty()) {
			int[] curr = q.poll();
			
			int x = curr[0], y = curr[1], z = curr[2];
			
			if (x == 0) {
				if (!ans.contains(z)) {
					ans.add(z);
				}
			}
			
			else {
				movewater(curr, 0, 1);
				movewater(curr, 0, 2);
			}
			
			if (y != 0) {
				movewater(curr, 1, 0);
				movewater(curr, 1, 2);
			}
			
			if (z != 0) {
				movewater(curr, 2, 0);
				movewater(curr, 2, 1);
			}		
		}
		
		Collections.sort(ans);
		for (int x: ans) {
			System.out.print(x+" ");
		}
		System.out.println();
	}

	private static void movewater(int[] temp, int from, int to) {
		int[] curr = Arrays.copyOf(temp, temp.length);
		
		if (curr[from] + curr[to] < nums[to]) {
			curr[to] = curr[from] + curr[to];
			curr[from] = 0;
		} else {
			curr[from] = curr[from] - (nums[to]-curr[to]);
			curr[to] = nums[to];
		}
		
		for (int[] row: list) {
			if (curr[0] == row[0] && curr[1] == row[1] && curr[2] == row[2]) {
				return;
			}
		}
		q.add(curr);
		list.add(curr);
	}
}