백준 2251 : 물통

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8 9 10

예제 출력 1 복사

1 2 8 9 10

 

• 풀이

 

A, B, C를 각각 정점에 들어갈 수 있는 최대값으로 보고 0, 0, C 부터 시작해서 갈 수 있는 모든 정점 중 C가 0인 정점을 찾으면 된다

 

각 정점의 상태를 State 클래스 안에서 생성자로 받아서 move 함수로 계산해서 물을 옮겨준다

 

class State{
    int[] x = new int[3];
    State(int[] _x){
        for (int i = 0; i < 3; i++) x[i] = _x[i];
    }

    State move(int from,int to,int[] Limit){
        // from 물통에서 to 물통으로 물을 옮긴다.
        int[] nX = new int[]{x[0], x[1], x[2]};
        if (x[from] + x[to] <= Limit[to]){  // 만약 from 을 전부 부을 수 있다면
            nX[to] = nX[from] + nX[to];
            nX[from] = 0;
        }

        else{  // from 의 일부만 옮길 수 있는 경우
            if (nX[from] - (Limit[to] - nX[to]) >= 0){
                nX[from] -= Limit[to] - nX[to];
                nX[to] = Limit[to];
            }
        }
        return new State(nX);
    }
}

 

bfs 함수에서는 큐에 현재 들어온 state의 a,b,c를 이용해서 move로 물을 옮겨주면서 탐색을 이어간다

static void bfs(int x1, int x2, int x3) {
        Queue<State> Q = new LinkedList<>();
        visit[x1][x2][x3] = true;
        Q.add(new State(new int[]{x1, x2, x3}));

        while (!Q.isEmpty()) {
            State st = Q.poll();
            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; // 같은 물통끼리 옮기는 경우는 의미 X
                    // i 번 물통에서 j 번 물통으로 물을 옮긴다.
                    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;
                        Q.add(nxt);
                    }
                }
            }
        }
    }

 

전체 코드

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

class State{
    int[] x = new int[3];
    State(int[] _x){
        for (int i = 0; i < 3; i++) x[i] = _x[i];
    }

    State move(int from,int to,int[] Limit){
        // from 물통에서 to 물통으로 물을 옮긴다.
        int[] nX = new int[]{x[0], x[1], x[2]};
        if (x[from] + x[to] <= Limit[to]){  // 만약 from 을 전부 부을 수 있다면
            nX[to] = nX[from] + nX[to];
            nX[from] = 0;
        }

        else{  // from 의 일부만 옮길 수 있는 경우
            if (nX[from] - (Limit[to] - nX[to]) >= 0){
                nX[from] -= Limit[to] - nX[to];
                nX[to] = Limit[to];
            }
        }
        return new State(nX);
    }
}

public class Main {

    static int[] Limit;
    static boolean[] possible;
    static boolean[][][] visit;
    static ArrayList<Integer> res;

    static void bfs(int x1, int x2, int x3) {
        Queue<State> Q = new LinkedList<>();
        visit[x1][x2][x3] = true;
        Q.add(new State(new int[]{x1, x2, x3}));

        while (!Q.isEmpty()) {
            State st = Q.poll();
            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; // 같은 물통끼리 옮기는 경우는 의미 X
                    // i 번 물통에서 j 번 물통으로 물을 옮긴다.
                    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;
                        Q.add(nxt);
                    }
                }
            }
        }
    }

    static void solution() {
        bfs(0, 0, Limit[2]);
        for (int i=0;i<=200;i++){
            if (possible[i]) res.add(i);
        }
        for (int x : res) System.out.print(x + " ");
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        Limit = new int[3];
        for (int i = 0; i < 3; i++) Limit[i] = in.nextInt();
        //visit 배열을 a,b,c 3개를 모두 탐색하기 위해서 3차원 배열로 작성해야한다
        visit = new boolean[201][201][201];
        possible = new boolean[201];
        res = new ArrayList<>();
        solution();
    }
}