문제 이해

물통 A,B,C가 주어지고, 현재 C만 가득 차 있다.
물통 A는 항상 최종적으로 비어있어야 한다.
이 때, C에 채울 수 있는 물의 양을 모두 구하라.

문제 풀이

조금 더 공간을 적게 사용하고 효율적으로 활용할 수 있는 방법이 있는지 고민해봤다. 하지만 그런 방법으로 생각해 낸 Case로 5개 정도 틀리자 조금 돌아가더라도 확실한 방법을 사용하기로 했다.

먼저 visit을 3차원 boolean형 Array로 표현했다.
이후 visit[A의 양][B의 양][C의 양]으로 처리하여, 만약 (A,B,C)로 물이 차있을 경우 visit[A][B][C] = true로 변환했다.

이후 모든 경우의 수를 고려해봤다.
이 때, DFS보다는 BFS가 Queue를 활용하기 때문에 구현이 조금 더 쉬울 것이고, DFS의 재귀함수 종료 조건을 설정하기 까다로워 BFS로 문제를 해결하였다.

만약 visit[A][B][C] = true일 경우 아무런 행동도 취하지 않는다(이미 확인한 것)
반대로 false일 경우 visit[A][B][C] = true로 이동시킨 이후 물을 이동시킬 수 있는 모든 경우의 수를 수행시켰다.
또한, A = 0일 때의 C는 정답이 될 수 있으므로 ArrayList에 집어넣었고, Queue가 비었을 때 ArrayList의 모든 답을 출력시켰다.

(중복은 없다. A = 0으로 고정이고, 총량은 고정되어 있으므로, 만약 C = k라면 B도 자동으로 고정된 값을 가지게 된다)

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static ArrayList<Integer> ans = new ArrayList<>();
	static int[] size = new int[3];
	static boolean[][][] visit = new boolean[201][201][201];
	
	//A : 0 B : 1, C: 2
	
	static int[] move(int from, int to, int[] state) {
        // from -> to 방향으로 물이 이동함
        // state : 현재 A,B,C 물통에 물이 담겨져 있는 현황
		int from_value = state[from];
		int to_value = state[to];
		int max_to = size[to];
		// from에 들어있는 물 양 : from_value
		// to에 넣을 수 있는 물 양 : size[to] - to_value
		
		int[] result = new int[3];
		for(int i =0;i<3;i++) result[i] = state[i];
		
		if(max_to-to_value>=from_value) { 
            // to에 넣을 수 있는 양 >= from에 들어 있는 양
			result[from] = 0;
			result[to] += from_value;
		}
		else {
            // to에 넣을 수 있는 양 < from에 들어 있는 양
			result[from] = from_value + to_value - max_to;
			result[to] = max_to;
		}
		
		return result;
	}
	
	static void bfs(int[] state) {
		
		Queue<int[]> queue = new LinkedList<>();
		queue.add(state);

		while(!queue.isEmpty()) {
			int[] tmp = queue.poll();
		
			if(visit[tmp[0]][tmp[1]][tmp[2]]) continue;
			
			visit[tmp[0]][tmp[1]][tmp[2]] = true;
			if(tmp[0]==0) ans.add(tmp[2]);
			
			queue.offer(move(0,1,tmp)); // A -> B
			queue.offer(move(0,2,tmp)); // A -> C
			queue.offer(move(1,0,tmp)); // B -> A
			queue.offer(move(1,2,tmp)); // B -> C
			queue.offer(move(2,0,tmp)); // C -> A
			queue.offer(move(2,1,tmp)); // C -> B
		}
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		size[0] = sc.nextInt();
		size[1] = sc.nextInt();
		size[2] = sc.nextInt();
		
		bfs(new int[] {0,0,size[2]});
		
		Collections.sort(ans);
		StringBuilder sb = new StringBuilder();
		for(int s:ans) {
			sb.append(s+" ");
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과

• 2,3,4,5번째 줄 틀렸습니다 : 효율적이라고 생각한 방법을 시도해보면서 틀렸다.