백준 2251번 물통(Java)

A, B, C 세개의 물통이 있고, 처음에는 A와 B물통에는 물이 비어 있고 C물통에만 물이 차있다. 

물통의 최대 용량이 input으로 주어지고, 어떤 물통에서 다른 물통으로 물을 따를 때는 다른 물통이 가득 찰 때까지 혹은, 따르는 물통의 물이 빌 때까지 따를 수 있다.

A물통이 비어 있을 때, C의 물통에 차있는 물의 양으로 가능한 것을 오름차순으로 출력해야한다.

물을 따르는 경우는 A->B, A->C, B->A, B->C, C->A, C->B 총 6가지 경우가 있다. 이 때, 현재 물통에 담긴 물의 양을 상태로 저장하여 한번 방문한 상태의 경우는 재방문 하지 않도록 BFS를 구현하여 문제를 풀어주면 된다.

나는 물의 양을 "-"로 연결하여 Key를 만들었고, Set을 이용해서 방문 여부를 체크했다. 예를 들어 처음 상태는 A,B가 비어있고, C만 차있는 상황이므로, (0,0,c)이고 key는 "0-0-c" 의 형태로 만들어진다.

아래는 내가 푼 Java Source이다. 

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

class State {
    int curA;
    int curB;
    int curC;

    public State(int a, int b, int c) {
        this.curA = a;
        this.curB = b;
        this.curC = c;
    }

    public String getKey() {
        return curA + "-" + curB + "-" + curC;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        // 8 9 10
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] spt = line.split(" ");
        int a = Integer.parseInt(spt[0]);
        int b = Integer.parseInt(spt[1]);
        int c = Integer.parseInt(spt[2]);
        Set<String> visited = new HashSet<>();
        Set<Integer> answer = new HashSet<>();

        Queue<State> q = new LinkedList<>();

        State init = new State(0, 0, c);
        q.add(init);
        visited.add(init.getKey());
        while (!q.isEmpty()) {
            State top = q.poll();
            if (top.curA == 0) {
                answer.add(top.curC);
            }
            // a -> b
            if (top.curA > 0 && top.curB < b) {
                int canMove = (b - top.curB);
                int move = Math.min(top.curA, canMove);
                int nextA = top.curA - move;
                int nextB = top.curB + move;
                State nextState = new State(nextA, nextB, top.curC);
                if (!visited.contains(nextState.getKey())) {
                    visited.add(nextState.getKey());
                    q.add(nextState);
                }
            }
            // a -> c
            if (top.curA > 0 && top.curC < c) {
                int canMove = (c - top.curC);
                int move = Math.min(top.curA, canMove);
                int nextA = top.curA - move;
                int nextC = top.curC + move;
                State nextState = new State(nextA, top.curB, nextC);
                if (!visited.contains(nextState.getKey())) {
                    // answer.add(nextC);
                    visited.add(nextState.getKey());
                    q.add(nextState);
                }
            }

            // b -> a
            if (top.curB > 0 && top.curA < a) {
                int canMove = (a - top.curA);
                int move = Math.min(top.curB, canMove);
                int nextB = top.curB - move;
                int nextA = top.curA + move;
                State nextState = new State(nextA, nextB, top.curC);
                if (!visited.contains(nextState.getKey())) {
                    visited.add(nextState.getKey());
                    q.add(nextState);
                }
            }
            // b -> c
            if (top.curB > 0 && top.curC < c) {
                int canMove = (c - top.curC);
                int move = Math.min(top.curB, canMove);
                int nextB = top.curB - move;
                int nextC = top.curC + move;
                State nextState = new State(top.curA, nextB, nextC);
                if (!visited.contains(nextState.getKey())) {
                    // answer.add(nextC);
                    visited.add(nextState.getKey());
                    q.add(nextState);
                }
            }
            // c -> a
            if (top.curC > 0 && top.curA < a) {
                int canMove = (a - top.curA);
                int move = Math.min(top.curC, canMove);
                int nextC = top.curC - move;
                int nextA = top.curA + move;
                State nextState = new State(nextA, top.curB, nextC);
                if (!visited.contains(nextState.getKey())) {
                    // answer.add(nextC);
                    visited.add(nextState.getKey());
                    q.add(nextState);
                }
            }
            // c -> b
            if (top.curC > 0 && top.curB < b) {
                int canMove = (b - top.curB);
                int move = Math.min(top.curC, canMove);
                int nextC = top.curC - move;
                int nextB = top.curB + move;
                State nextState = new State(top.curA, nextB, nextC);
                if (!visited.contains(nextState.getKey())) {
                    // answer.add(nextC);
                    visited.add(nextState.getKey());
                    q.add(nextState);
                }
            }
        }
        List<Integer> answerList = answer.stream().collect(Collectors.toList());
        answerList.sort((Integer aa, Integer bb) -> {
            return aa - bb;
        });
        answerList.stream().forEach(aa -> {
            System.out.print(aa + " ");
        });
        System.out.println();
    }
}