물통 2251

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

이 문제를 처음에 A, B, C 물통을 하나하나 별개의 노드로 생각하고 풀려고 생각했는데 어떻게 구현해야 할지 막막했다.
풀이를 봤는데 A, B, C 에 물의 양이 차있는 상태를 하나의 노드로 삼아서 풀어야한다
그래서 State 라는 클래스를 만들었고 길이가 3 인 w 배열로 물의양을 표현했다

다른 사람들의 풀이를 봐도 이해되지 않는부분이 있었는데
A->B, A->C, B->A, B->C, C->A, C->B 로 6가지로 물을 옮기는 경우로 표현할 수 있다는 설명이 이해가 되지 않았다.

강의를 보면서 다시 이해하였고 정리해본다

처음엔 ABC 에 물의양 상태는 0, 0, 10 이다.
그리고 이 상태에서 물을 옮길 수 있는 경우는
A->B, A->C, B->A, B->C, C->A, C->B 이 있을 것이다. 일단 코드적으로는 6가지의 경우를 시도하되
if 로 예외처리를 해야한다 물의양이 없는 A,B 물통은 예외처리가 되고
C->A, C->B 만 가지를 뻗어나갈 것이다

이제
C->A 에서 발생하는 경우를 보자 C->A 옮겼으니 물의 상태는 8, 0, 2 가 될것이다. B물통은 비어 있으니
A->B, A->C, C->A, C->B 로 가지를 뻗어나갈 것이다

C->B 에서 발생하는 경우를 보자 C->B 옮겼으니 물의 상태는 0, 9, 1 가 될것이다 A물통은 비어 있으니
C->A, C->B 로 가지를 뻗어나갈 것이다

이런식으로 6진트리로 뻗어나가되 물을 주는 물통의 물이 없는 경우는 가지치기가 될것이다

import java.io.*;
import java.util.*;


public class Main
{
    static class State
    {
        int[] w = new int[3];

        public State() {
        }

        public State(int a, int b, int c) {
            this.w[0] = a;
            this.w[1] = b;
            this.w[2] = c;
        }
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int A = Integer.parseInt(input[0]);
        int B = Integer.parseInt(input[1]);
        int C = Integer.parseInt(input[2]);

        int[] capacity = {A, B, C};
        boolean[][][] visit = new boolean[A+1][B+1][C+1];
        HashSet<Integer> ans = new HashSet<>();

        bfs(new State(0, 0, capacity[2]), visit, capacity, ans);

        Object[] temp = ans.toArray();
        Arrays.sort(temp);
        Arrays.stream(temp).forEach(i-> System.out.print(i+" "));
    }

    public static void bfs(State state, boolean[][][] visit, int[] capacity, HashSet<Integer> ans)
    {
        Queue<State> que = new LinkedList<>();

        que.add(state);
        visit[state.w[0]][state.w[1]][state.w[2]] = true;

        if(state.w[0] == 0)
            ans.add(state.w[2]);

        while(que.isEmpty() == false)
        {
            State cur = que.poll();

            for(int i = 0; i < 3; ++i)
            {
                for(int j = 0; j < 3; ++j)
                {
                    for(int k = 0; k < 3; ++k)
                    {
                        if(i != j && i != k && j != k
                        && cur.w[j] > 0)//물통에 물이 있을때 옮겨담을 수 있다
                        {
                        	//ijk 012,021,102,120,201,210 순으로 들어옴
                            NextState(cur, i, j, k, que, visit, capacity, ans);
                        }
                    }
                }
            }
        }
    }

    private static void NextState(State cur, int i, int j, int k, Queue<State> que, boolean[][][] visit, int[] capacity, HashSet<Integer> ans)
    {

        //from j -> k
        if(cur.w[j] <= (capacity[k] - cur.w[k]))
        {
            State newState = new State();
            newState.w[i] = cur.w[i];
            newState.w[j] = 0;
            newState.w[k] = cur.w[j] + cur.w[k];
            if(visit[newState.w[0]][newState.w[1]][newState.w[2]] == false)
            {
                que.add(newState);
                visit[newState.w[0]][newState.w[1]][newState.w[2]] = true;

                if(newState.w[0] == 0)
                    ans.add(newState.w[2]);
            }

        }
        else
        {
            State newState = new State();
            newState.w[i] = cur.w[i];
            newState.w[j] = cur.w[j] - (capacity[k] - cur.w[k]);
            newState.w[k] = capacity[k];

            if(visit[newState.w[0]][newState.w[1]][newState.w[2]] == false)
            {
                que.add(newState);
                visit[newState.w[0]][newState.w[1]][newState.w[2]] = true;

                if(newState.w[0] == 0)
                    ans.add(newState.w[2]);
            }
        }
    }
}