[백준 / BOJ] 2251 물통 (cpp)

문제

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

2251번: 물통

각각 부피가 A, B, C인 물통이 있고 A, B는 비어있으며 C는 꽉 차있다.

물을 이동 시킬때는 항상 하나의 물통이 꽉차거나 빌때까지만 옮길 수 있다.

이때, 물통 A가 비어있을때, 물통 C에 있을수 있는 물의 양을 모두 구하는 문제다.

---

풀이

DFS로 풀어도 풀리는 문제다.

A, B, C의 최대 용량이 각각 200이므로, 3차원 체크 배열로 이미 방문한 상태를 재 방문 하지 않도록 만들어주면, 최악의 경우 200*200*200번 반복으로 풀 수 있다. 

 

따라서, 시간복잡도는 O(N^3)이 나온다.

 

알고리즘은 다음과 같다.

1. 현재 물의 상태 check[A][B][C] 를 이전에 방문했는지 확인한다.

-> 방문했다면, 이 경로는 이미 이전에 모두 방문했음을 알 수 있으므로(나는 DFS로 코드를 작성했음), 더 이상 들어가지 않고 return 한다.

2. 물통 A의 값이 0 이라면 물통 C의 값을 저장한다.

3. 물을 움직인다.

 

위 과정을 더 이상 방문할 경우가 없을때까지 반복하면 풀리는 문제이다.

이때, 물을 움직이는 경우의 수 는 총 6가지로 다음과 같다.

 

1. 물을 A -> B로 이동시키는 경우

2. 물을 A -> C로 이동시키는 경우

3. 물을 B -> A로 이동시키는 경우

4. 물을 B -> C로 이동시키는 경우

5. 물을 C -> A로 이동시키는 경우

6. 물을 C -> B로 이동시키는 경우

 

물을 A1 -> A2로 이동할때는 다음과 같은 식을 세울 수 있다.

 

- 물을 받은 후 A2의 물의 양 = A2가 이미 갖고있던 물의 양 + min(A2가 받을수 있는 물의 양, A1이 줄 수 있는 물의 양)

- 물을 준 후 A1의 물의 양 = max(0, A1이 갖고있던 물의 양 - A2가 받을 수 있는 물의 양)

 

위 식을 이용해서 재귀 코드를 작성하면 아래와 같이 나온다.

void solve(int a, int b, int c){
    if(check[a][b][c]) return;
    check[a][b][c] = true;
    if(a == 0 && !visited[c]){
        vec.push_back(c);
        visited[c] = true;
    }
    int capA = A - a;
    int capB = B - b;
    int capC = C - c;
    solve(max(0, a - capC), b, c + min(a, capC)); // a to c
    solve(max(0, a - capB), b + min(a, capB), c); // a to b
    solve(a, max(0, b - capC), c + min(b, capC)); // b to c
    solve(a + min(b, capA), max(0, b - capA), c); // b to a
    solve(a + min(c, capA), b, max(0, c - capA)); // c to a
    solve(a, b + min(c, capB), max(0, c - capB)); // c to b
}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/2251%20물통/main.cpp

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃