[BOJ/JAVA] 백준 2251 : 물통 (자바)

문제 정보

  문제명   - 물통
  난이도   - 골드 V
문제 번호 - 2251번

---

문제 링크

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

2251번: 물통

---

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

---

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

---

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

---

예제 입력/출력

예제 입력	예제 출력
8 9 10	1 2 8 9 10

---

알고리즘 분류

● 그래프 이론
● 그래프 탐색
● 너비 우선 탐색
● 깊이 우선 탐색

---

소스코드

package Lv3_Gold;

import java.io.*;
import java.util.*;
/**
 * @author HanHoon
 * @category 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
 * https://www.acmicpc.net/problem/2251
 */
public class BOJ_G5_2251_물통 {
    static int A, B, C;
    static ArrayList<Integer> result = new ArrayList<>();
    static class Bottle{
        int a;
        int b;
        int c;

        public Bottle(int a, int b, int c){
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
    public static void bfs(){
        Queue<Bottle> queue = new LinkedList<>();
        boolean[][][] isVisited = new boolean[A+1][B+1][C+1];

        // 초기 상태
        queue.add(new Bottle(0, 0, C));

        while(!queue.isEmpty()){
            Bottle current = queue.poll();
            // 현재 상태에서 체크한 적이 있다면 continue;
            if(isVisited[current.a][current.b][current.c]) continue;

            // 첫 번째 물통이 비어 있을 때, 세 번째 물통에 담겨있을 수 있는 물의 양 추가
            if(current.a == 0)
                result.add(current.c);

            isVisited[current.a][current.b][current.c] = true;

            // A->B
            if (current.a + current.b <= B)
                queue.add(new Bottle(0, current.a + current.b, current.c));
            else
                queue.add(new Bottle(current.a + current.b - B, B, current.c));
            // A->C
            if (current.a + current.c <= C)
                queue.add(new Bottle(0, current.b, current.a + current.c));
            else
                queue.add(new Bottle(current.a + current.c - C, current.b, C));
            // B->A
            if (current.a + current.b <= A)
                queue.add(new Bottle(current.a + current.b, 0, current.c));
            else
                queue.add(new Bottle(A, current.a + current.b - A, current.c));
            // B->C
            if (current.b + current.c <= C)
                queue.add(new Bottle(current.a, 0, current.b + current.c));
            else
                queue.add(new Bottle(current.a, current.b + current.c - C, C));
            // C->A
            if (current.a + current.c <= A)
                queue.add(new Bottle(current.a + current.c, current.b, 0));
            else
                queue.add(new Bottle(A, current.b, current.a + current.c - A));
            // C->B
            if (current.b + current.c <= B)
                queue.add(new Bottle(current.a, current.b + current.c, 0));
            else
                queue.add(new Bottle(current.a, B, current.b + current.c - B));
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder str = new StringBuilder();

        // 세 정수 A, B, C (물병의 최대 용량)
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        bfs();

        Collections.sort(result);
        for(int n : result)
            str.append(n + " ");

        System.out.print(str);
        br.close();
    }
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---