[JAVA] 백준 2251 물통_DFS

 

문제 : 

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

 

 

접근 : 

 

 - 물통 상태를 저장하는 클래스를 생성한다.

 

 - 물통  a 부터 남은 물의 양이 있으면 b 또는 c 로 옮긴다. 만약 옮긴 후의 상태가 한번이라도 같은 적이 있는 경우에는 물을 붓지 않는다.

 

 - a가 비어 있을때, c 의 물의 상태를 TreeSet 으로 저장하여 모든 수를 출력한다.

 

 

코드구현 1 (물통Set 전체를 클래스로 구현) :

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static Set<BottleState> visited;
    private static int[] bottle_size;
    private static Set<Integer> ans;

    public static class BottleState{
        private int[] nums;
        public BottleState(int[] nums){
            this.nums = nums;
        }

        public int getState(int idx){
            return idx < nums.length ? this.nums[idx] : 0;
        }
        public void updateState(int idx, int value){
            this.nums[idx] = value;
        }
        public int[] copyState(){
            return this.nums.clone();
        }
        public int getSize(){
            return nums.length;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            BottleState that = (BottleState) o;
            return Arrays.equals(nums, that.nums);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(nums);
        }
    }

    private static void dfs(BottleState bottleState){
        visited.add(bottleState);
        if(bottleState.getState(0) == 0) ans.add(bottleState.getState(bottleState.getSize()-1));

        int remain_target;
        int remian_start;

        for(int i = 0 ; i < bottleState.getSize() ; i++){
            if(bottleState.getState(i) == 0) continue;

            for(int j = 0 ; j < bottleState.getSize() ; j++){
                if(i == j) continue;

                if(bottleState.getState(i) + bottleState.getState(j) > bottle_size[j]){
                    //부었을때, 대상의 물통이 넘치는 경우
                    remain_target = bottle_size[j];
                    remian_start = bottleState.getState(i) + bottleState.getState(j) - bottle_size[j];
                }else{
                    remain_target = bottleState.getState(i) + bottleState.getState(j);
                    remian_start = 0;
                }

                BottleState next = new BottleState(bottleState.copyState());
                next.updateState(j, remain_target);
                next.updateState(i, remian_start);

                if(visited.contains(next)) continue;
                dfs(next);
            }// for
        }// for
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] inputs =  br.readLine().split(" ");
        int size = inputs.length;
        ans = new TreeSet<>();
        bottle_size = new int[size];

        for(int i = 0 ; i < size; i++) bottle_size[i] = Integer.parseInt(inputs[i]);

        visited = new HashSet<>();
        dfs(new BottleState(new int[]{0, 0, bottle_size[size-1]}));

        for(int n : ans) sb.append(n).append(' ');

        System.out.println(sb);
        br.close();
    }
}

코드구현 1 (물통 1개를 클래스로 구현) :

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static Bottle[] bottles;
    private static int bottle_num;
    private static Set<Integer> ans;
    private static Set<List<Integer>> visited;

    public static class Bottle{
        private int size;
        private int state;
        public Bottle(int size, int state){
            this.size = size;
            this.state = state;
        }
        public int getSize() {
            return size;
        }
        public int getState() {
            return state;
        }
        public void addState(int newState){
            state += newState;
        }
    }


    private static void dfs(){
        if(bottles[0].getState() == 0) ans.add(bottles[2].getState());

        for(int from = 0 ; from < bottle_num ; from++){
            if(bottles[from].getState() == 0) continue;

            for(int to = 0 ; to < bottle_num ; to++){
                if(to == from) continue;
                int move;

                if((bottles[from].getState() + bottles[to].getState()) > bottles[to].getSize()){
                    //넘치는 경우
                    move = bottles[to].getSize() - bottles[to].getState();
                }else{
                    move = bottles[from].getState();
                }

                bottles[from].addState(-1*move);
                bottles[to].addState(move);

                if(!visited.add(Arrays.asList(bottles[0].getState(), bottles[1].getState(), bottles[2].getState()))){
                    bottles[from].addState(move);
                    bottles[to].addState(-1*move);
                    continue;
                }
                dfs();
                bottles[from].addState(move);
                bottles[to].addState(-1*move);
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] inputs =  br.readLine().split(" ");
        bottle_num = inputs.length;
        ans = new TreeSet<>();
        bottles = new Bottle[3];
        visited = new HashSet<>();

        for(int i = 0 ; i < bottle_num-1; i++) bottles[i] = new Bottle(Integer.parseInt(inputs[i]), 0);
        int amount = Integer.parseInt(inputs[bottle_num-1]);
        bottles[bottle_num-1] = new Bottle(amount, amount);
        visited.add(Arrays.asList(bottles[0].getState(), bottles[1].getState(), bottles[2].getState()));
        dfs();

        for(int n : ans) sb.append(n).append(' ');

        System.out.println(sb);
        br.close();
    }
}

 

 

* 두가지 구현 방법의 성능, 메모리 차이는 없음