[KOI 2017] 고등부 1번. 물통

▣ 문제 출처  ─  2017년도 한국 정보올림피아드(KOI) 전국 본선 고등부 1번 문제

▣ 알고리즘 분류  ─  BFS / 수학 / 구현

▣ solved.ac 기준 난이도  ─  Gold II

 

 

2017년도 고등 KOI 1번으로 나온 문제다. (문제의 내용은 여기에서 확인할 수 있다.)

 

  문제의 내용을 대략 요약하면 다음과 같다: 용량이 다른 두 개의 빈 물통 A, B가 있고, 각 시행마다 하나의 물통을 가득 채우거나, 비우거나, 한 물통에서 다른 물통으로 물을 옮기는 행위를 할 수 있다고 한다. 물통 A, B의 용량 $a,\, b\,(a < b)$와 최종 상태 $(c,\, d)$가 주어질 때, $(0,\, 0)$에서 $(c,\, d)$로 만들기 위한 최소 시행 수를 구하는 문제다. 만약 최종 상태로 만들 수 없다면 $-1$을 출력하면 된다. 수학 창의력 퀴즈 같은 데서 자주 나오는 유형의 문제기에 아마도 꽤 친숙한 문제가 아닐까 싶다. 물론 이 문제는 정보 올림피아드 문제긴 하지만….

 

  일단 문제에서 최소 시행 횟수를 구하라 하였기 때문에, 대부분 BFS를 가장 먼저 떠올릴 것이다. 우선 각 시행마다 할 수 있는 행동들을 정리해 보면, (시행 직전에 물통 A에 $x$만큼, 물통 B에 $y$만큼 담겨있다고 하자.)

 

① A를 채운다. $(x,\, y) → (a,\, y)$                         ② B를 채운다. $(x,\, y) → (x,\, b)$
 ③ A를 비운다. $(x,\, y) → (0,\, y)$                         ④ B를 비운다. $(x,\, y) → (x,\, 0)$ 
⑤ A의 물을 B로 옮긴다. $(x,\, y) → (x - k,\, y + k)$ (단, $k = \min(x,\, b - y)$)
 ⑥ B의 물을 A로 옮긴다. $(x,\, y) → (x + k,\, y - k)$ (단, $k = \min(a - x,\, y)$)

 

이렇게 여섯 가지가 있다. 따라서 $(0,\, 0)$부터 시작하여 6가지 방식을 모두 해 보면 최소 시행 수를 구할 수 있겠…으나, 문제는 너무 느리다. 시간복잡도가 무려 $\mathcal O(6^{ans})$이나 된다. 시행 횟수가 10만 넘어가도 시간 제한에 아슬아슬하다.

 

  이를 좀 더 개선해 보자. 위 6가지 시행을 잘 고찰해 보면, 한 가지 특징을 발견할 수 있다. 바로 각 시행마다 어느 하나의 물통은 무조건 비어 있거나 가득 차 있다는 것이다! 즉 어떤 순서로 어떤 시행을 하든지 1) A가 비어 있거나 2) B가 비어 있거나 3) A가 가득 차 있거나 4) B가 가득 차 있거나 이렇게 네 가지 경우 중 하나라는 것이다. (그래서 사실 최종 상태 $(c,\, d)$ 또한 이 조건을 만족해야 답이 존재한다.) 이때 각 경우에 대해 나머지 물통에는 0 이상 해당 물통 용량 이하의 물만이 존재할 수 있으므로, 시행 중에 나올 수 있는 모든 경우의 수(= 탐색해야 하는 경우의 수)는 최대 $4b$ 가지뿐이라는 사실을 도출할 수 있다(∵ 문제 조건에서 $a$보다 $b$가 크므로).

 

  따라서 $b \times 4$ 크기의 배열을 선언하여 모든 칸을 INF로 초기화한 뒤, BFS 방식으로 모든 경우를 다 탐색하며 각 배열의 칸에 해당 상태로 도달하는 최소 횟수를 저장하는 방식의 풀이를 생각해 볼 수 있다. 만약 해당 배열 칸에 이미 INF가 아닌 값이 저장되어 있다면, 이미 더 적은 시행으로 해당 상태에 도달했다는 뜻이므로 그냥 넘어가면 된다. 그렇게 모든 경우를 다 탐색했을 때, $(c,\, d)$에 대한 배열값이 INF라면 $-1$을, INF가 아니라면 그 값을 그대로 출력하면 끝이다! 이때의 시간 복잡도는 $\color{orange}{\mathcal O(4b)}$가 되기에, 본 문제를 여유롭게 해결할 수 있다.

 

  다만 함수 호출에 따른 오버헤드도 있고, 시간 복잡도에 상수가 있는 관계로 시간이 0 ms가 아닌 게 좀 찜찜하다. (이 방법을 이용한 내 코드는 12ms가 나왔다.) 좀 더 효율적인 방법이 없을까?

 

  그런데 생각해 보니, 매 시행마다 저 6가지 행위를 모두 할 수 있는 것이 아니지 않은가? 우선 초기 상태 $(0,\, 0)$을 생각해 보면, 이 상태에서 할 수 있는 것은 ① 혹은 ②뿐이다. 먼저 ①을 시행한 경우부터 살펴 보자. 그럼 이제 상태가 $(0,\, 0)$에서 $(a,\, 0)$으로 바뀌었다. 이 상태에서 할 수 있는 행위는 단 하나, ⑤밖에 없다! ①은 이미 A에 물이 가득 차 있어서 안 되고, ②번 시행을 하게 되면 물통 A와 B 둘 다에 물이 가득 차게 되어 다시 두 물통 중 하나를 비우는 수밖에 없다. 이러면 채웠다 비우게 되는 셈이라 최소 횟수가 되지 않으므로 ②는 기각된다. (단, 주어진 최종 상태가 $(a,\, b)$일 경우에는 해당되지 않는다. 따라서 이 경우를 예외로 처리해 주어야 한다.) ③은 다시 $(0,\, 0)$으로 돌아가게 되어 이 또한 최소 횟수가 되지 않아 기각. ④, ⑥은 물통 B가 이미 비어 있어서 불가능하다. 따라서 가능한 것은 ⑤뿐임을 알 수 있다.

 

  이제 상태는 $(a,\, 0)$에서 $(0,\, a)$가 되었다. 여기에서 할 수 있는 시행을 또 생각해 보면, 이번엔 ①만 가능하다. ②를 하면 $(0,\, b)$가 되는데, $(0,\, b)$는 초기 상태 $(0,\, 0)$에서 바로 물통 B를 채우면 되므로 역시 최소 횟수가 아니다. ③, ⑤는 물통 A가 이미 비어 있어서 불가능하고, ④는 $(0,\, 0)$으로 돌아가게 되어 기각, ⑥은 $(a,\, 0)$으로 돌아가게 되어 기각된다. 즉 가능한 건 ①밖에 없다. 그리고 상태는 $(0,\, a)$에서 $(a,\, a)$로 바뀌게 된다. 이 상태에서 또 할 수 있는 시행을 골라 보면, 위와 마찬가지로 ⑤만 가능하다. 그리고 여기서 상태는 두 가지로 갈라지게 된다.

 

• 첫째로 $2a ≤ b$인 경우, 상태는 $(a,\, a)$에서 $(0,\, 2a)$로 바뀌게 되고, 또 다시 가능한 시행은 ①뿐이기에 $(a,\, 2a)$가 된다. 다시, 시행 ⑤만 가능하며 상태는 똑같이 두 가지($3a ≤ b$인 경우와 $3a > b$인 경우)로 나뉜다. 이후 이러한 논의가 계속해서 반복된다.
• 둘째로 $2a > b$인 경우, 상태는 $(a,\, a)$에서 $(2a - b,\, b)$가 되고, 이때 가능한 시행은 ④밖에 없다. 그래서 상태는 $(2a - b,\, 0)$이 된다. 이 경우 역시 가능한 시행은 ⑤밖에 없으며, 상태는 다시 $(0,\, 2a - b)$로 바뀌었다가, 유일하게 가능한 시행 ①을 하여 $(a,\, 2a - b)$가 되고, 다시 시행 ⑤만 가능하게 되고 이후 상태가 두 가지($3a - b ≤ b$인 경우와 $3a - b > b$인 경우)로 나뉜다. 역시 이 과정이 계속 반복된다.

  보면 알겠지만, 시행 ①과 ⑤가 반복되고 이따금 시행 ④를 해 주는 형태만이 가능한 것을 알 수 있다. 즉 A를 채우고, 이걸 B로 옮기고, 다시 A에 물 채우고, B로 옮기고… 를 반복하게 된다. 그러다가 물통 B가 가득 차게 되면 B를 비우고 다시 이를 반복한다. 더욱이, 이러한 반복은 반드시 유한한 시행 안에 끝나게 된다. 구체적으로, 이 시행은 물통 A에 있는 물을 모두 물통 B로 부었을 때(다시 말해서 물통 A가 비었을 때) 물통 B가 가득 차는 순간 끝나게 된다. 왜냐하면 그 뒤에 물통 B를 비우게 되면 다시 $(0,\, 0)$으로 돌아오기 때문이다. 그리고 이러한 순간은 앞서 말했듯, 반드시 존재하게 된다. (왜일까? 한 번 생각해 보라.)

 

  그렇다면 최초 $(0,\, 0)$ 상태에서 A에 물을 채우는 게 아닌, B에 물을 채우는 경우(시행 ②를 한 경우)는 어떨까? 사실 이 경우의 시행 순서는, 정확히 위 시행의 역과정이 된다! 실제로 $(0,\, 0) → (0, b)$로 시행을 시작할 경우를 위와 같이 전개를 해 보면 정확히 위와 정반대가 된다. (위에서 했던 대로 이 과정을 직접 해 보길 바란다.) 따라서 시행을 하면서 나타나는 모든 경우는 $(0,\, 0)$에서 시작하여 $(0,\, 0)$으로 끝나는 사이클 내의 경우들뿐이며, 우리는 이 한 사이클만 조사해 보면 끝난다! 또한 한 사이클의 총 시행 수를 $T$라 하고, 초기 상태에서 시행 ①을 했을 경우에 최종 상태에 도달하기까지 걸린 시행 수를 $k$라고 하면, 시행 ②를 했을 경우에 최종 상태에 도달하기까지 걸리는 시행 수는 거꾸로 $(T - k)$가 된다. 즉 $k$와 $(T - k)$ 중 더 작은 값이 답이 된다! 만약 주어진 최종 상태가 사이클을 도는 동안 나타나지 않는다면 그 상태로 도달할 수 없다는 뜻이기에 $-1$을 출력하면 된다.

 

  이를 코드로 구현하면 다음과 같다. 코드의 시간 복잡도는 $\color{magenta}{\mathcal O(b)}$. 두 번째 방법에 비해 4배 작은 연산량을 가지며, 아래 코드는 함수 호출을 할 필요가 없기에 시간이 더 적게 걸린다. (심지어 메모리도 거의 사용하지 않는다!) 실제로 해당 코드는 코드업과 BOJ에서 0 ms로 돌아간다.

#include <stdio.h>
#define min(p, q) (p < q ? p : q)

int a, b, c, d;
int x, y, k, T;   // x: A에 들어 있는 물의 양, y: B에 들어 있는 물의 양

int main()
{
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if (a == c && b == d) return puts("2");   // 우선 최종 상태가 (a, b)라면 2를 출력
    while (1) {
        if (y == b) y = 0;   // B가 가득 찼으면 비운다.
        else if (!x) x = a;  // A가 비었으면 채운다.
        else if (x + y < b) y += x, x = 0;  // A의 물을 B로 모두 옮길 수 있는 경우
        else x -= b - y, y = b;             // 그렇지 않은 경우
        T++;
        if (x == c && y == d) k = T;
        if (!x && !y) break;               // A, B 모두 비었으면 반복문 종료
    }
    printf("%d", k ? min(k, T - k) : -1);  // k와 T - k 중 최솟값 출력.
    return 0;
}