[알고리즘] 그래프탐색 강의 풀이 - 백준 2251

1. 문제

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

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

2. 입력

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

3. 풀이

1. 문제의 탐색영역

초기 상태 : (0,0,c)

0<=a<=A
0<=b<=B
0<=c<=C

최대 201 201 201 = 약 8*10^6

• 물을 붓는 행위
  (a,b,c) -> (a',b',c')
  한가지 상태가 정점이고 물을 부어서 다른 상태로 이동하는 것을 간선이라고 하면?
  -> 그래프
  
  (방향이 있는 그래프)

2. 탐색

초기 상태 : (0,0,c)
그래프를 탐색하면서 a가 0인 정점을 찾으면 됨
-> 그래프 탐색 문제로 바뀜

3. 시간복잡도

정점 : O(810^6)
간선 : O(810^6*6)
(한 정점에 대해 최대 6가지의 행위 선택 가능)

BFS든 DFS든 시간복잡도는 O(8*10^6)

4. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//그래프 정점
class State{
    int[] x;

    //생성자
    State(int[] _x){
        x = new int[3];
        for(int i=0;i<3;i++){
            x[i] = _x[i];
        }
    }

    //물을 옮기고 나서의 상태를 return 함수
   State move(int from, int to, int[] limit){
        int[] nx = new int[]{x[0],x[1],x[2]};

        //넘치는 경우
        //넘치는 양을 제외하고 to로 옮김김
       if(x[from]+x[to]>=limit[to]){
            nx[from] -= limit[to] -x[to];
            nx[to] = limit[to];
        }
        //넘치지 않는 경우
        //from의 모든 물을 to로 옮김
        else{
            nx[to] += nx[from];
            nx[from] = 0;
        }
        return new State(nx);
    }

}


public class bottle_2251 {

    static int[] limit;
    static boolean[] possible;
    static boolean[][][] visit;

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        StringBuilder sb = new StringBuilder();

        limit = new int[3];
        for(int i=0;i<3;i++){
            limit[i] = Integer.parseInt(st.nextToken());
        }
        visit = new boolean[205][205][205]; //그래프 방문 표시 배열
        possible = new boolean[205]; //정답으로 가능한 값들 위치에 true로 표시됨

        bfs(0,0,limit[2]);

        for(int i=0;i<=limit[2];i++){
            if(possible[i])
                sb.append(i).append(' ');
        }

        System.out.println(sb);

    }

    //그래프 bfs로 돌면서 A가 0인 정점 탐색
    //dfs로 풀어도 됨
    static void bfs(int x1, int x2, int x3){
        Queue<State> queue = new LinkedList<>();

        visit[x1][x2][x3] = true;

        queue.add(new State(new int[]{x1,x2,x3}));

        while(!queue.isEmpty()){
            State st = queue.poll();
            //A가 0일 때 정답배열에 현재 C 물통에 들어있는 양을 인덱스로 하는곳에 true 표시
           if(st.x[0] == 0)
                possible[st.x[2]] = true;

           for(int from=0;from<3;from++){
               for(int to=0;to<3;to++){
                    if(from==to) continue;
                    State nxt = st.move(from, to, limit);

                    //방문한 적 없는 노드면
                    if(!visit[nxt.x[0]][nxt.x[1]][nxt.x[2]]){
                        visit[nxt.x[0]][nxt.x[1]][nxt.x[2]] = true;
                        queue.add(nxt);
                    }
               }
           }

        }
    }

}