[백준] 2251. 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

구조화

A, B, C가 담을 수 있는 최대 리터가 200이기 때문에 isVisited를 201로 두었음

컵의 개수만큼 입력을 받고 DFS를 진행했음

DFS에서는 A, B, C가 이동하는 케이스 마다 변화하는 값을 담아 DFS로 코드를 구현했다.

코드 구현

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

public class Main {
    static int A, B, C;
    static int[] cup;
    static boolean[][] isVisited;
    static Set<Integer> set;
    public static void main(String[] args) throws Exception  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        isVisited = new boolean[201][201];
        cup = new int[3];
        set = new TreeSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < 3 ; i ++) 
        	cup[i] = stoi(st.nextToken());
        
        dfs(0, 0, cup[2]);
        
        for(int tmp : set)
        	System.out.print(tmp + " ");
    }

    private static void dfs(int a, int b, int c) {
        // 종료조건 이전의 C 값과 동일하거나, A가 비어있을 경우
        if(isVisited[a][b]) return;
        
        if(a==0) set.add(c);
        
        isVisited[a][b] = true;
        
        // a컵 -> b컵
        if(a+b > cup[1])
        	dfs((a+b) - cup[1], cup[1], c);
        else
        	dfs(0, a+b, c);
        
        // b컵 -> a컵
        if(a+b > cup[0])
        	dfs(cup[0], (a+b) - cup[0], c);
        else
        	dfs(a+b, 0, c);
        
        // c컵 -> a컵
				if(a+c > cup[0]) {
					dfs(cup[0], b, a+c-cup[0]);
				}
				else
					dfs(a+c, b, 0);
        
        // c컵 -> b컵
        if(b+c > cup[1])
        	dfs(a, cup[1], b+c-cup[1]);
        else
        	dfs(a, b+c, 0);
        
        // a컵 -> c컵
        dfs(a, 0, b+c);
        // b컵 -> c컵
        dfs(0, b, a+c);
        
    }

static int stoi(String s) {
    return Integer.parseInt(s);
}
}