[BaekJoon] 14867 물통 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/14867

2.  문제

요약

• 용량이 다른 두 개의 빈 물통 A, B가 있는데 이 물통들에 물을 채우고 비우는 일을 반복하여 두 물통을 원하는 상태가 되도록 만들고자 합니다.
• 물통 이외에는 물의 양을 정확히 잴 수 있는 방법이 없으며, 가능한 작업은 다음과 같은 세 종류가 전부입니다.
  • [F(x) : Fill x] : 물통 x에 물을 가득 채웁니다. (물을 채우기 전에 물통 x가 비어있는지 여부는 관계 없습니다. 다른 물통은 그대로 둡니다)
  • [E(x) Empty x] : 물통 x의 물을 모두 버립니다. (다른 물통은 그대로 둡니다)
  • [M(x, y): Move water from x to y] : 물통 x의 물을 물통 y에 붓습니다. 이때 만약 물통 x에 남아있는 물의 양이 물통 y에 남아있는 빈 공간보다 적거나 같다면 물통 x의 물을 물통 y에 모두 붓습니다. 만약 물통 x에 남아있는 물의 양이 물통 y에 남아있는 빈 공간보다 많다면 부을 수 있는 만큼 최대로 부어 물통 y를 꽉 채우고 나머지는 물통 x에 남깁니다.
• 두 물통의 용량과 원하는 최종 상태를 입력으로 받은 후, 두 물통이 비어있는 상태에서 시작하여 최종 상태에 도달하기 위한 최소 작업 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 물통 A의 용량을 나타내는 정수 a와 물통 B의 용량을 나타내는 정수 b, 0보다 크거나 같고 a보다 작거나 같은 최종 상태에서 물통 A에 남겨야하는 물의 용량을 나타내는 정수 c와 0보다 크거나 같고 b보다 작거나 같은 최종 상태에서 물통 B에 남겨야 하는 물의 용량을 나타내는 정수 d가 주어집니다.
• 출력: 첫 번째 줄에 목표 상태에 도달하는 최소 작업 수를 나타내는 정수를 출력합니다. 만약 목표 상태에 도달하는 방법이 없다면 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int MAXSIZE = 100000;
    static int a, b, c, d;

    static void input() {
        Reader scanner = new Reader();

        a = scanner.nextInt();
        b = scanner.nextInt();
        c = scanner.nextInt();
        d = scanner.nextInt();
    }

    static void solution() {
        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Bottles> queue = new LinkedList<>();
        HashSet<Bottles> visited = new HashSet<>();

        queue.offer(new Bottles(0, 0, 0));
        visited.add(new Bottles(0, 0, 0));

        while(!queue.isEmpty()) {
            Bottles cur = queue.poll();

            if(cur.A == c && cur.B == d) return cur.moveNum;

            if(visited.add(new Bottles(a, cur.B, cur.moveNum + 1))) queue.offer(new Bottles(a, cur.B, cur.moveNum + 1));
            if(visited.add(new Bottles(cur.A, b, cur.moveNum + 1))) queue.offer(new Bottles(cur.A, b, cur.moveNum + 1));
            if(visited.add(new Bottles(0, cur.B, cur.moveNum + 1))) queue.offer(new Bottles(0, cur.B, cur.moveNum + 1));
            if(visited.add(new Bottles(cur.A, 0, cur.moveNum + 1))) queue.offer(new Bottles(cur.A, 0, cur.moveNum + 1));

            int extraB = b - cur.B, remainA, remainB;
            if(cur.A > extraB) {
                remainA = cur.A - extraB;
                remainB = b;
            } else {
                remainA = 0;
                remainB = cur.B + cur.A;
            }
            if(visited.add(new Bottles(remainA, remainB, cur.moveNum + 1))) queue.offer(new Bottles(remainA, remainB, cur.moveNum + 1));

            int extraA = a - cur.A;
            if(cur.B > extraA) {
                remainB = cur.B - extraA;
                remainA = a;
            } else {
                remainB = 0;
                remainA = cur.B + cur.A;
            }
            if(visited.add(new Bottles(remainA, remainB, cur.moveNum + 1))) queue.offer(new Bottles(remainA, remainB, cur.moveNum + 1));
        }

        return -1;
    }

    static class Bottles {
        int A, B, moveNum;

        public Bottles(int a, int b, int moveNum) {
            A = a;
            B = b;
            this.moveNum = moveNum;
        }

        @Override
        public boolean equals(Object o) {
            Bottles bottles = (Bottles)o;

            if(A == bottles.A && B == bottles.B) return true;
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(A, B);
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 모든 가능한 작업들에 대해 BFS를 통해 최소 작업 수를 구합니다.
  • 우선 각 통에 물을 가득 채우는 경우와 물을 비우는 경우에 대해 방문 체크를 진행하고 아직 물통 A와 물통 B에 남아있는 물의 양에 대해 방문하지 않았다면 다음 탐색을 위해 Queue에 넣습니다.
  • A에서 B로 물을 붓는 경우, B에서 A로 물을 붓는 경우에 대해 계산합니다.
    • 예를 들어, A에서 B로 물을 붓는 경우를 생각해봤을 때, B에 남아있는 공간을 확인하고 B에 남아있는 공간이 A에 있는 물의 양보다 작거나 같다면 물통 B에는 물이 가득 찰 것이므로 B에 물을 가득 채우고 A에는 B에 남아있는 공간만큼 물을 뺀 이후의 물이 남아있게 합니다.
    • 반대로 B에 남아있는 공간이 A에 있는 물의 양보다 크다면 물통 A는 비우고 A에 있는 물의 양만큼 B에 넣습니다.
  • 각 경우를 계산한 후에 아직 방문되지 않은 상태들에 대해서 Queue에 각 경우를 넣습니다.