[java 백준] 실버 1/2251번 물통

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

2251번: 물통

import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;
 
public class Main {
    public static class Water {
        int a;
        int b;
        int c;
 
        public Water(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
 
    }
 
    public static int a, b, c;
    public static ArrayList<Integer> ans = new ArrayList<Integer>();
    public static boolean[][][] visited = new boolean[201][201][201];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
 
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
 
        Queue<Water> queue = new LinkedList<Water>();
 
        queue.add(new Water(0, 0, c));
 
        while (!queue.isEmpty()) {
            Water water = queue.poll();
 
            if (visited[water.a][water.b][water.c]) {
                continue;
            } else {
                visited[water.a][water.b][water.c] = true;
            }
 
            if (water.a == 0) {
                ans.add(water.c);
            }
 
            // a,b물통
 
            if (water.a + water.b > a) {
                // 1-2 -> 2-5
                // a 다 채우고 나머지는 b로
                queue.add(new Water(a, water.a + water.b - a, water.c));
            } else {
                // 전부 a로 옮기기
                queue.add(new Water(water.a + water.b, 0, water.c));
 
            }
 
            if (water.a + water.b > b) {
                // b 다 채우고 나머지는 a로
                queue.add(new Water(water.a + water.b - b, b, water.c));
            } else {
                queue.add(new Water(0, water.a + water.b, water.c));
 
            }
 
            // b,c물통
 
            if (water.b + water.c > b) {
                queue.add(new Water(water.a, b, water.b + water.c - b));
            } else {
                queue.add(new Water(water.a, water.b + water.c, 0));
            }
 
            if (water.b + water.c > c) {
                // c다 채우고 나머지는 b로
                queue.add(new Water(water.a, water.b + water.c - c, c));
            } else {
                queue.add(new Water(water.a, 0, water.b + water.c));
            }
 
            // a,c물통
 
            if (water.a + water.c > a) {
 
                // a다 채우고 나머지는 c로
                queue.add(new Water(a, water.b, water.a + water.c - a));
            } else {
                queue.add(new Water(water.a + water.c, water.b, 0));
            }
 
            if (water.a + water.c > c) {
                // c 다채우고 나머지는 a로
                queue.add(new Water(water.a + water.c - c, water.b, c));
            } else {
                queue.add(new Water(0, water.b, water.a + water.c));
            }
 
        }
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int x : ans) {
            treeSet.add(x);
        }
 
        Iterator iter = treeSet.iterator();
        while (iter.hasNext()) {
            System.out.print(iter.next() + " ");
        }
 
    }
 
}

 

문제를 풀면서 중요한거 2가지

 

1) 문제를 제대로 읽자!

첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 구하는건데 이걸 제대로 안보고 계속 c용량만 출력하니까 틀렸습니다만 떴다.. 

 

2) 이건 아쉬운건데 문제를 풀어낼 수 있는 방법이 6가지라는걸 빨리 파악하지 못했다.

사실 조금만 직접 써봐도 알수 있는 거였다.(심지어 직접 써봤는데도 파악하지 못함..ㅋ)

지금까지 완전탐색 문제를 풀면서 느낀건 케이스가 유한하게 정해져있고 거기서 풀어낼 수 있는 방법의 가지 수도 유한했다. 남은 완전탐색 문제도 이 생각을 잊지말고 풀자.

 

그래서 이문제에서 케이스 분류를 해보면

a,b물통끼리 -> a에서 b로/ b에서 a로

 

b,c 물통끼리->b에서 c로/c에서 b로

 

c,a 물통끼리->a에서 c로/c에서 a로

 

더 세부적으로 파고 들면

 

1)a,b 물통끼리의 경우 (a,b만 생각해준다)

a물통+b물통> a이면  a물통을 다 채워주고 나머지는 b로

a물통+b물통<a 이면 a에 몰아주고, b는 0

 

a물통+b물통>b 이면 b 물통 다 채워주고 나머지는 a로

a물통+b물통<b이면 b에 몰아주고 a는 0

 

이걸 3번 반복해주면 끝 

 

Tree set

중복 제거하고 오름차순으로 정렬해주는 자료구조라 한다. 

https://coding-factory.tistory.com/555

[Java] 자바 TreeSet 사용법 & 예제 총정리

참고 사이트 

 

https://fl0wering.tistory.com/13

2251번 : 물통 [Java]