[JAVA] 백준 2251 - 물통

 

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

2251번: 물통

• 처음에는 수학적으로 풀고싶다고 생각했는데
• 쉽지않아서 그냥 탐색하는 식으로 풀기로 했다

 

bfs로 풀기로함. 이유는 다음과 같다

1. 한 번 부으면 무조건 다 부어야함
2. 물통은 3개 밖에 없음
3. 붓다보면 나올 수 있는 케이스가 그렇게 많지 않을 것이다
4. 또한 부피가 최대 200임 -> 정말 많지 않을듯

 

 

내 풀이

class Case {
    int A;
    int B;
    int C;

    public Case(int a, int b, int c) {
        A = a;
        B = b;
        C = c;
    }
}

public class Main {
    static int A;
    static int B;
    static int C;

    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());

        boolean[][][] visit = new boolean[A+1][B+1][C+1];

        TreeSet<Integer> treeSet = new TreeSet<>();

        Queue<Case> queue= new LinkedList<>();
        queue.add(new Case(0, 0, C));

        while (!queue.isEmpty()) {
            Case current = queue.poll();

            if (visit[current.A][current.B][current.C] == false) {
                visit[current.A][current.B][current.C] = true;

                if (current.A == 0) {
                    treeSet.add(current.C);
                }

                // C -> A
                if (current.C != 0 && current.A != A) {
                    int diff =  getDiff(current.C, A, current.A);
                    queue.add(new Case(current.A + diff, current.B, current.C - diff));
                }

                // C -> B
                if (current.C != 0 && current.B != B) {
                    int diff = getDiff(current.C, B, current.B);
                    queue.add(new Case(current.A, current.B+diff, current.C - diff));
                }

                // B -> A
                if (current.B != 0 && current.A != A) {
                    int diff = getDiff(current.B, A, current.A);
                    queue.add(new Case(current.A + diff, current.B-diff, current.C));
                }

                // B -> C
                if (current.B != 0 && current.C != C) {
                    int diff = getDiff(current.B, C, current.C);
                    queue.add(new Case(current.A, current.B - diff, current.C + diff));
                }

                // A -> C
                if (current.A != 0 && current.C != C) {
                    int diff = getDiff(current.A, C, current.C);
                    queue.add(new Case(current.A - diff, current.B, current.C + diff));
                }

                // A -> B
                if (current.A != 0 && current.B != B) {
                    int diff = getDiff(current.A, B, current.B);
                    queue.add(new Case(current.A - diff, current.B+diff, current.C));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int num: treeSet) {
            sb.append(num + " ");
        }
        
        System.out.println(sb);
    }

    private static int getDiff(int currentStart, int maxEnd, int currentEnd) {
        int diff =  (maxEnd - currentEnd);
        if (diff > currentStart) {
            diff = currentStart;
        }

        return diff;
    }
}

• 굉장히 부끄럽고 더러운 코드다
• A, B, C에 대한 방문여부를 visit 배열에 넣었다
• C -> A, C -> B, B -> A, B -> C, ... 모든 경우를 queue에 넣어주었다
• queue가 빌 때까지 수행함

 

중복코드를 어떻게 삭제할까 고민하다 구글링을 해봤다

 

 

다른 풀이1

https://loosie.tistory.com/513

•  dfs와 bfs 두 가지 방법으로 풀이하셨다
• 중복코드를 0, 1, 2 인덱스를 이용하여 for문으로 만들어 구현하셨다 -> 중복코드가 줄어 실수할 위험은 줄어드는 듯
• 물통의 양은 일정하기 때문에 visit를 2차원 배열로만 해도 충분하다 -> visit[A][B] 만 해도 C는 결정되니까 메모리가 절약됨

 

 

다른 풀이2

https://velog.io/@chosj1526/%EB%B0%B1%EC%A4%80-2251-%EB%AC%BC%ED%86%B5-JAVA

• 책을 참고하신 것 같다
• 이 분도 A와 B의 2차원배열로 푸셨다
• receiver와 sender를 지정하여 중복코드를 확 줄이셨다 -> 좋은 방법인듯

 

 

 

개선한 나의 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

class Case {
    int valueA;
    int valueB;

    public Case(int valueA, int valueB) {
        this.valueA = valueA;
        this.valueB = valueB;
    }

    private Case() {}

    public int getValue(int i, int C) {
        if (i < 0 || i > 2) {
            throw new IllegalArgumentException();
        }

        switch(i) {
            case 0:
                return valueA;
            case 1:
                return valueB;
            case 2:
                return C - valueA - valueB;
        }

        return 0;
    }

    public Case getNew(int startIdx, int endIdx, int diff) {
        Case c = new Case(this.valueA, this.valueB);

        if (startIdx == 0) {
            c.valueA = this.valueA - diff;
        } else if (startIdx == 1) {
            c.valueB = this.valueB - diff;
        }

        if (endIdx == 0) {
            c.valueA = this.valueA + diff;
        } else if (endIdx == 1) {
            c.valueB = this.valueB + diff;
        }

        return c;
    }
}

public class Main {
    static int[] start = {0,0,1,1,2,2};
    static int[] end = {1,2,0,2,0,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int valueA = Integer.parseInt(st.nextToken());
        int valueB = Integer.parseInt(st.nextToken());
        int valueC = Integer.parseInt(st.nextToken());
        int[] values = {valueA, valueB, valueC};

        boolean[][] visit = new boolean[valueA +1][valueB +1];

        TreeSet<Integer> treeSet = new TreeSet<>();

        Queue<Case> queue= new LinkedList<>();
        queue.add(new Case(0, 0));

        while (!queue.isEmpty()) {
            Case current = queue.poll();

            if (visit[current.valueA][current.valueB] == false) {
                visit[current.valueA][current.valueB] = true;

                if (current.valueA == 0) {
                    treeSet.add(valueC - current.valueB);
                }

                for (int i =0; i<6; i++) {
                    int startIdx = start[i];
                    int endIdx = end[i];

                    int startValue = current.getValue(startIdx, valueC);
                    int endValue = current.getValue(endIdx, valueC);

                    if (startValue != 0 && endValue != values[endIdx]) {
                        int diff = getDiff(startValue, values[endIdx], endValue);
                        queue.add(current.getNew(startIdx, endIdx, diff));
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int num: treeSet) {
            sb.append(num + " ");
        }

        System.out.println(sb);
    }

    private static int getDiff(int currentStart, int maxEnd, int currentEnd) {
        int diff =  (maxEnd - currentEnd);
        if (diff > currentStart) {
            diff = currentStart;
        }

        return diff;
    }
}

 

1. visit배열을 2차원으로 수정
2. 물통 케이스를 담는 클래스도 A, B만 저장하도록 수정