[알고리즘][DFS][2251] 물통

[알고리즘][DFS][2251] 물통

 

문제

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

 

 

 

풀이

모든 경우를 탐색하여 풀어야 하는 문제입니다. 또한 문제에서 한 물통이 비워질 때 까지 붓거나 다른 물통이 가득 찰 때까지 물을 부을 수 있다는 것을 고려하여 풀어야 합니다. 물이 넘칠 때와 그렇지 않을 때를 고려하여 문제를 풀었고, A에서 C로, B에서 C로 물을 옮길 때에는 물이 넘칠 가능성이 없기 때문에 IF절을 쓰지 않았습니다! 

 

코드

package algorithm_DFS;

import java.util.Scanner;

public class q_2251 {
    static boolean[][] visited = new boolean[201][201];
    static boolean[] ans = new boolean[201];
    static int a,b,c;
    public static void main(String[] args) {
        Scanner scan= new Scanner(System.in);
        a = scan.nextInt();
        b = scan.nextInt();
        c = scan.nextInt();
        
        dfs(0,0,c);
        
        for(int i=0;i<201;i++) {
            if(ans[i]) {
                System.out.print(i+" ");
            }
        }
    }
    
    public static void dfs(int va,int vb, int vc) {
        if(visited[va][vb]) {
            return;
        }
        
        if(va==0) {
            ans[vc]=true;
        }
        
        visited[va][vb] = true;
        
        // a --> b
        if(va+vb>b) {
            dfs((va+vb)-b,b,vc);
        }else {
            dfs(0,va+vb,vc);
        }
        
        // b --> a
        if(vb+va>a) {
            dfs(a,(vb+va)-a,vc);
        }else {
            dfs(vb+va,0,vc);
        }
        
        // c --> a
        if(vc+va>a) {
            dfs(a,vb,(vc+va)-a);
        }else {
            dfs(vc+va,vb,0);
        }
        
        // c --> b
        if(vc+vb>b) {
            dfs(va,b,(vc+vb)-b);
        }else {
            dfs(va,vc+vb,0);
        }
        
        dfs(va,0,vb+vc);
        dfs(0,vb, va+vc);
    }

}