[BOJ 2251] 물통 (Java, BFS/DFS)

 

---

문제 링크

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

2251번: 물통

---

풀이

- 문제에는 표현되어 있지 않지만, 물통의 상태(=정점), 물을 붙는 행위 (=간선) 으로 정의하여 풀어야 하는 그래프 문제 

 

1) 입력으로 A B C 물통의 사이즈가 정해짐

2) 초기 C 물통만 가득찬 상태이고, 나머지 비어있는 상태에서 시작 

 

3) 각각 다른 물통에 물을 붙는 행위를 하여 A = 0 일때 C 물통의 상태(결과)값을 구해 오름차순으로 출력

 

 

이때 정점(1 <= A, B, C <= 200)은 최대 200 * 200 * 200 = 8 * 10^6 = 800만 

 

간선의 경우

- A 에서 B, C 로 물을 부을 수 있음

- B 에서 A, C 로 물을 부을 수 있음

- C 에서 A, B 로 물을 부을 수 있음 

(자기자신은 제외하여 총 6개의 간선을 가짐)

 

정점 : O(8 *  10^6)

간선 : O(8 * 10^6 * 6 )

하나의 정점은 6개의 간선을 가진 형태( 단반향 그래프 )

 BFS, DFS 둘다 동일한 시간 복잡도 가짐

 

---

제출 코드 

 

DFS로 할 경우 

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int [] LIMIT = new int[3];
    static boolean[][][] VISIT = new boolean[201][201][201];

    static List<Integer> RESULT = new ArrayList<>();
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < 3; i++) {
            LIMIT[i] = Integer.parseInt(st.nextToken());
        }
    }

    static class State {
        public int[] liquid;

        public State(int[] _liquid) {
            liquid = new int[3];
            for(int i = 0; i < 3; i++) {
                liquid[i] = _liquid[i];
            }
        }

        public State moveTo(int from, int to, int[] _limit) {
            int[] _liquid = new int[]{liquid[0], liquid[1], liquid[2]};

            if(_liquid[from] + _liquid[to] >= _limit[to]) {
                _liquid[from] -= (_limit[to] - _liquid[to]);
                _liquid[to] = _limit[to];
            } else {
                _liquid[to] += _liquid[from];
                _liquid[from] = 0;
            }

            return new State(_liquid);
        }
    }

    static void dfs(State state) {
        VISIT[state.liquid[0]][state.liquid[1]][state.liquid[2]] = true;
        if(state.liquid[0] == 0) RESULT.add(state.liquid[2]);

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

                State next = state.moveTo(from, to, LIMIT);
                if(VISIT[next.liquid[0]][next.liquid[1]][next.liquid[2]]) continue;

                dfs(next);
            }
        }
    }

    static void pro() {
        dfs(new State(new int[]{0, 0, LIMIT[2]}));

        Collections.sort(RESULT);
        for(int n : RESULT) sb.append(n).append(" ");

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }


}

 

BFS로 할 경우

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int [] LIMIT = new int[3];
    static boolean[][][] VISIT = new boolean[201][201][201];

    static List<Integer> RESULT = new ArrayList<>();
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < 3; i++) {
            LIMIT[i] = Integer.parseInt(st.nextToken());
        }
    }

    static class State {
        public int[] liquid;

        public State(int[] _liquid) {
            liquid = new int[3];
            for(int i = 0; i < 3; i++) {
                liquid[i] = _liquid[i];
            }
        }

        public State moveTo(int from, int to, int[] _limit) {
            int[] _liquid = new int[]{liquid[0], liquid[1], liquid[2]};

            if(_liquid[from] + _liquid[to] >= _limit[to]) {
                _liquid[from] -= (_limit[to] - _liquid[to]);
                _liquid[to] = _limit[to];
            } else {
                _liquid[to] += _liquid[from];
                _liquid[from] = 0;
            }

            return new State(_liquid);
        }
    }

    static void bfs(State state) {
        Queue<State> que = new LinkedList<>();
        que.add(state);
        VISIT[state.liquid[0]][state.liquid[1]][state.liquid[2]] = true;

        while(!que.isEmpty()) {
            State current = que.poll();
            if(current.liquid[0] == 0) RESULT.add(current.liquid[2]);

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

                    State next = current.moveTo(from, to, LIMIT);
                    if(VISIT[next.liquid[0]][next.liquid[1]][next.liquid[2]]) continue;

                    VISIT[next.liquid[0]][next.liquid[1]][next.liquid[2]] = true;
                    que.add(next);
                }
            }
        }
    }

    static void pro() {
        bfs(new State(new int[]{0, 0, LIMIT[2]}));

        Collections.sort(RESULT);
        for(int n : RESULT) sb.append(n).append(" ");

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }

}