• 백준 2251번 물통 :: 마이구미
    알고리즘 풀이/그래프 2017. 10. 3. 23:04
    반응형

    이 글은 백준 알고리즘 문제 2251번 "물통" 을 풀이한다.

    BFS 또는 DFS를 통해 문제를 해결할 수 있다.

    본인은 DFS로 풀이하겠다. (BFS가 좀 더 효율적이다)

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


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

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


    처음에는 규칙 또는 최소공배수와 같은 수학 공식을 통해 풀 수 있을 거라 생각했다.

    하지만, 단순히 모든 경우를 탐색해야하는 문제가 된다.


    물통의 갯수는 3개로 정해져있기에, 모든 경우는 다음과 같다.


    A -> B = 물통 A의 물을 물통 B로 옮기는 경우

    A -> C

    B -> A

    B -> C

    C -> A

    C -> B


    주의할 점은 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 부을 수 있다는 점을 기억해야한다.


    그래프 알고리즘 문제 풀이 - 그래프 문제 카테고리

    Github - https://github.com/hotehrud/acmicpc/tree/master/graph


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    static boolean[][] visited = new boolean[201][201];
    static boolean[] ans = new boolean[201];
    static int a, b, c;
     
    private void solve() {
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
     
        dfs(00, c);
     
        for (int i = 0; i < 201; i++) {
            if (ans[i]) {
                System.out.print(i + " ");
            }
        }
    }
     
    public static void dfs(int ca, int cb, int cc) {
        if (visited[ca][cb]) {
            return;
        } 
     
        if (ca == 0) {
            ans[cc] = true;
        }
     
        visited[ca][cb] = true;
     
        // a -> b
        if (ca + cb > b) {
            dfs((ca + cb) - b, b, cc);
        } else {
            dfs(0, ca + cb, cc);
        }
        // b -> a
        if (cb + ca > a) {
            dfs(a, (cb + ca) - a, cc);
        } else {
            dfs(cb + ca, 0, cc);
        }
        // c -> a
        if (cc + ca > a) {
            dfs(a, cb, (cc + ca) - a);
        } else {
            dfs(cc + ca, cb, 0);
        }
        // c -> b
        if (cc + cb > b) {
            dfs(ca, b, (cc + cb) - b);
        } else {
            dfs(ca, cc + cb, 0);
        }
        // b -> c, a -> c
        // a + b = c 이기 때문에, c가 넘칠 일이 없다.
        dfs(ca, 0, cb + cc);
        dfs(0, cb, ca + cc);
    }
    cs


    반응형

    TAG

    댓글 0

Designed by Tistory.