[백준] 14867: 물통 - JAVA

in Algorithm on 자료 구조

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

풀이

용량이 정해진 물통을 주어진 용량으로 맞춰야 한다.

할 수 있는 동작은 정해져있는데

  1. 물통 x에 물을 가득 채운다.

  2. 물통 x의 물을 모두 버린다.

  3. 물통 x의 물을 물통 y에 붓는다.

위의 세가지를 통해 용량을 맞출 때 최소 작업 수를 구해야 한다.

두 개의 물통을 0, 0상태에서 시작하여 bfs탐색을 통해 정해진 양을 맞추면 return했다.

이때 방문처리를 하기 위해 class를 만들어 set으로 체크하였다.

set의 contains 메서드를 이용할 때 객체의 경우 비교하기 위해서는 class에 equals와 hashcode를 오버라이드해야 했다.

이 점만 알고 있다면 크게 어려운 것 없는 문제였다.

메모리: 146500KB

시간: 500ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        int a;
        int b;
        int cnt;

        public Node(int a, int b, int cnt) {
            this.a = a;
            this.b = b;
            this.cnt = cnt;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Node)) {
                return false;
            }
            Node node = (Node) o;
            return this.a == node.a && this.b == node.b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }
    }

    static int A, B, C, D;
    static Queue<Node> queue;
    static Set<Node> visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        int ans = bfs();

        System.out.println(ans);
    }

    private static int bfs() {
        queue = new LinkedList<>();
        visit = new HashSet<>();
        queue.add(new Node(0, 0, 0));
        visit.add(new Node(0, 0, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.a == C && node.b == D) {
                return node.cnt;
            }

            // Fill a
            operation(A, node.b, node.cnt + 1);
            // Fill b
            operation(node.a, B, node.cnt + 1);
            // Empty a
            operation(0, node.b, node.cnt + 1);
            // Empty b
            operation(node.a, 0, node.cnt + 1);

            int total = node.a + node.b;
            // a -> b
            if (total < B) {
                operation(0, total, node.cnt + 1);
            } else {
                operation(total - B, B, node.cnt + 1);
            }
            // b -> a
            if (total < A) {
                operation(total, 0, node.cnt + 1);
            } else {
                operation(A, total - A, node.cnt + 1);
            }
        }

        return -1;
    }

    private static void operation(int oa, int ob, int ocnt) {
        if (visit.contains(new Node(oa, ob, 0))) {
            return;
        }

        visit.add(new Node(oa, ob, 0));
        queue.add(new Node(oa, ob, ocnt));
    }

}