백준 2251번 물통 :: 마이구미

이 글은 백준 알고리즘 문제 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

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(0, 0, 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);
}