[BaekJoon] 2251 물통 (Java)

1.  문제 링크

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

2.  문제

요약

• 각각 부피가 A, B, C 리터인 세 개의 물통이 있고 처음에는 앞의 두 물통은 비어있고 세 번째 물통(C 리터)은 가득 차 있습니다.
• 어떤 물통에 들어있는 물을 다른 물통으로 쏟을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 통이 가득 찰 때까지 물을 부을 수 있습니다.
• 첫 번째 물통(A 리터)이 비어있을 때, 세 번째 물통(C 리터)에 담겨있을 수 있는 물의 양을 모두 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 200보다 작거나 같은 세 정수 A, B, C가 주어집니다.
• 출력: 첫 번째 줄에 공백으로 답을 구분하여 출력합니다. 각 용량은 오름차순으로 정렬합니다.

3.  소스코드

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

public class Main {
	static int[] size;
	static boolean[][] visited;
	static TreeSet<Integer> result;
	
	static void input() {
		Reader scan = new Reader();
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		size = new int[] {a, b, c};
		visited = new boolean[201][201];
		result = new TreeSet<Integer>();
	}
	
	static void solution(int a, int b, int c) {
		if(visited[a][b]) return;
		if(a == 0)
			result.add(c);
		visited[a][b] = true;
		
        // 첫 번째 물통에서 두 번째 물통에 물을 쏟는 경우
		if(a + b > size[1]) {
			solution(a + b - size[1], size[1], c);
		} else {
			solution(0, a + b, c);
		}
		
        // 두 번째 물통에서 첫 번째 물통에 물을 쏟는 경우
		if(a + b > size[0]) {
			solution(size[0], a + b - size[0], c);
		} else {
			solution(a + b, 0, c);
		}
		
        // 세 번째 물통에서 첫 번째 물통에 물을 쏟는 경우
		if(a + c > size[0]) {
			solution(size[0], b, a + c - size[0]);
		} else {
			solution(a + c, b, 0);
		}
		
        // 세 번째 물통에서 두 번째 물통에 물을 쏟는 경우
		if(b + c > size[1]) {
			solution(a, size[1], b + c - size[1]);
		} else {
			solution(a, b + c, 0);
		}
		
        // 두 번째 물통에서 세 번째 물통에 물을 쏟는 경우
		solution(a, 0, b + c);
        // 첫 번째 물통에서 세 번째 물통에 물을 쏟는 경우
		solution(0, b, a + c);
	}
	
	public static void main(String[] args) {
		input();
		solution(0, 0, size[2]);
		for(int r : result)
			System.out.print(r + " ");
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• size라는 1차원 배열에 A, B, C 각각의 용량을 저장해놓습니다.
• DFS 진행 시에 방문된 곳인지 확인하기 위한 2차원 배열 visited를 생성합니다. 이는 A와 B에 대한 2차원 배열입니다. 즉, 행을 A의 물의 양, 열을 B의 물의 양이라고 생각합니다. A와 B의 물의 양을 알게 되면 자연적으로 C의 물의 양을 알 수 있기 때문에 이렇게 설정합니다.
  • 예를 들어, visited[a][b]라면 A의 물의 양이 a이고 B의 물의 양이 b일 때인 경우를 방문했는지를 나타냅니다.
• solution이라는 함수를 이용하여 DFS를 구현하는데, 해당 함수는 현재 A의 물의 양 a, 현재 B의 물의 양 b, 현재 C의 물의 양 c를 인자로 받고 재귀함수 호출을 통해 DFS를 구현합니다.
• 만약 visited[a][b]가 true라면, 즉 이미 방문되었다면 진행되었던 과정이기에 해당 과정에 대한 결과는 이미 반영되었으므로 재귀함수 호출을 멈춥니다.
• 만약 visited[a][b]가 false이고 a가 0이라면, 첫 번째 물통이 비었다는 뜻이므로 세 번째 물통에 담겨있을 수 있는 물의 양을 나타내는 TreeSet 자료구조에 c값을 넣습니다. TreeSet을 이용하는 이유는 이전에 들어왔던 값은 다시 들어오지 못하고 값들이 오름차순으로 정렬이 되어 문제에서 원하는 것과 일치하기 때문에 사용합니다.
• 위 두 경우 모두 아니라면 우선 A, B의 물의 양이 a, b인 경우를 현재 방문하였으므로 visited[a][b]의 값을 true로 변경해주고 한 물통에서 다른 한 물통으로 물을 쏟는 작업을 DFS를 통해 진행합니다.
• 각 경우에 대해 재귀함수를 통해 작업을 진행하고 모든 경우가 완료되었을 때의 TreeSet에 있는 값들이 세 번째 물통에 담겨있을 수 있는 물의 양이 됩니다.