[백준]#14867 물통

SeungBird·2021년 5월 20일
0

⌨알고리즘(백준)

목록 보기
337/401

문제

용량이 다른 두 개의 빈 물통 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에 남긴다.

예를 들어, 물통 A와 B의 용량이 각각 2리터와 5리터라고 하자. 두 물통 모두 빈 상태에서 시작하여 최종적으로 물통 A에는 2리터, 물통 B에는 4리터 물을 남기길 원할 경우, 다음과 같은 순서로 작업을 수행하면 총 8회의 작업으로 원하는 상태에 도달할 수 있다.

(0,0)→[F(B)]→(0,5)→[M(B,A)]→(2,3)→[E(A)]→(0,3)→[M(B,A)]→(2,1)→[E(A)]→(0,1)→[M(B,A)]→(1,0)→[F(B)]→(1,5)→[M(B,A)]→(2,4)

하지만, 작업 순서를 아래와 같이 한다면 필요한 작업 총 수가 5회가 된다.

(0,0)→[F(A)]→(2,0)→[M(A,B)]→(0,2)→[F(A)]→(2,2)→[M(A,B)]→(0,4)→[F(A)]→(2,4)

두 물통의 용량과 원하는 최종 상태를 입력으로 받은 후, 두 물통이 비어 있는 상태에서 시작하여 최종 상태에 도달하기 위한 최소 작업 수를 구하는 프로그램을 작성하시오.

입력

표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최종 상태에서 물통 B에 남겨야 하는 물의 용량을 나타내는 정수 d(0 ≤ d ≤ b)가 공백으로 분리되어 한 줄에 주어진다.

출력

목표 상태에 도달하는 최소 작업 수를 나타내는 정수를 표준 출력으로 출력한다. 만약 목표 상태에 도달하는 방법이 없다면 –1을 출력한다.

예제 입력 1

3 7 3 2

예제 출력 1

9

예제 입력 2

2 5 0 1

예제 출력 2

5

예제 입력 3

3 5 2 4

예제 출력 3

-1

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int max_a;
    static int max_b;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        max_a = Integer.parseInt(input[0]);
        max_b = Integer.parseInt(input[1]);
        int c = Integer.parseInt(input[2]);
        int d = Integer.parseInt(input[3]);

        bfs(c, d);
    }

    public static void bfs(int c, int d) {
        Queue<Pair> queue = new LinkedList<>();
        HashSet<Pair> visited = new HashSet<>();
        visited.add(new Pair(0, 0, 0));
        queue.add(new Pair(0, 0, 0));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(temp.a==c && temp.b==d) {
                System.out.println(temp.cnt);
                return;
            }

            if(temp.a<max_a) {        //F(a)
                Pair p = new Pair(max_a, temp.b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.b<max_b) {    //F(b)
                Pair p = new Pair(temp.a, max_b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.a>0) {    //E(a)
                Pair p = new Pair(0, temp.b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.b>0) {      //E(b)
                Pair p = new Pair(temp.a, 0, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.a+temp.b<=max_a) {    //M(b, a)
                Pair p = new Pair(temp.a+temp.b, 0, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            else {
                Pair p = new Pair(max_a, temp.a+temp.b-max_a, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.a+temp.b<=max_b) {    //M(a, b)
                Pair p = new Pair(0, temp.a+temp.b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            else {
                Pair p = new Pair(temp.a+temp.b-max_b, max_b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }
        }

        System.out.println(-1);
    }

    public static class Pair {
        int a;
        int b;
        int cnt;

        public Pair(int a, int b, int cnt) {
            this.a = a;
            this.b = b;
            this.cnt = cnt;
        }
        
        /////////중복 확인을 위한 메소드 
        
        @Override
        public boolean equals(Object o) {
            Pair p = (Pair) o;

            return (p.a == this.a && p.b == this.b);
        }

        @Override
        public int hashCode() {
            return (""+a+b).hashCode();
        }
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글