프로그래머스-양과늑대

프로그래머스 - 양과 늑대

---

문제 설명

문제 풀이

풀이 설명

0번 노드에서 출발하여, 연결된 다른 노드로 이동한다
이동된 노드에서 늑대의 개수가 양의 개수보다 같거나 크면은 종료된다.

만약 연결된 노드가 없다면 다른 이동 가능한 노드에서 체크한다

최소로 이동하며 양의 개수를 파악하는 것이 아닌 최대로 얻을 수 있는 양의 개수를 파악

코드 작성

        int[] animalInfo = null;
        Map<String, String> treeInfo = new HashMap<>();
        Queue<Map<String, String>> queue = new LinkedList<>();
        List<Integer> resultList = new ArrayList<>();
        Function<String, List> splitToList = (x) -> new ArrayList<>(Arrays.stream(x.split(",")).filter(z -> !z.isEmpty()).distinct().collect(Collectors.toList()));
        BiFunction<List<String>, String, String> listToJoiningString = (x, z) -> x.stream().filter(y -> !y.equals(z)).collect(Collectors.joining(","));

        public int solution(int[] info, int[][] edges) {
            animalInfo = info;
            arrayTreeIntoMap(edges);

            addQeueue(0,0,"0","");
            findHighestSheep();

            int answer = resultList.stream().mapToInt(Integer::intValue).max().getAsInt();
            System.out.println("answer = " + answer);
            return answer;
        }

        void arrayTreeIntoMap(int[][] edges){
            for(int[] edge : edges){
                String key = String.valueOf(edge[0]);
                String value = String.valueOf(edge[1]);
                if(!treeInfo.containsKey(key)){
                    treeInfo.put(key, value);
                }else{
                    String orDefault = treeInfo.get(key);
                    orDefault += ","+value;
                    treeInfo.put(key, orDefault);
                }
            }
        }

        void addQeueue(int sheep, int wolf, String current, String possibleNode){
            Map<String, String> map = new HashMap<>();
            map.put("sheep", String.valueOf(sheep));
            map.put("wolf", String.valueOf(wolf));
            map.put("current", current);
            map.put("possibleNode", possibleNode);

            queue.add(map);
        }

        void findHighestSheep(){
            while(queue.size() > 0){
                Map poll = queue.poll();
                String sheep = (String) poll.get("sheep");
                String wolf = (String) poll.get("wolf");
                String current = (String) poll.get("current");
                String possibleNode = (String) poll.get("possibleNode");
                findNextNode(Integer.parseInt(sheep), Integer.parseInt(wolf), current, possibleNode);
            }
        }

        void findNextNode(int sheep, int wolf, String current, String possibleNode){
            int typeAnimal = animalInfo[Integer.parseInt(current)];

            if (typeAnimal == 0) sheep++;
            else wolf++;

            if(wolf >= sheep) resultList.add(sheep);
            else{
                List<String> possibleNodeList = splitToList.apply(possibleNode);

                if(treeInfo.containsKey(current)){
                    List<String> goNodeList = splitToList.apply(treeInfo.get(current));
                    goNodeList.addAll(possibleNodeList);

                    for(int i = 0; i < goNodeList.size(); i++){
                        String goNode = goNodeList.get(i);
                        addQeueue(sheep, wolf, goNode, listToJoiningString.apply(goNodeList, goNode));
                    }

                }else{
                    if(possibleNodeList.isEmpty()) resultList.add(sheep);
                    else{
                        for(int i = 0; i < possibleNodeList.size(); i++){
                            List<String> copyPossibleNode = new ArrayList<>(possibleNodeList);
                            copyPossibleNode.remove(i);
                            addQeueue(sheep, wolf, possibleNodeList.get(i), listToJoiningString.apply(copyPossibleNode, ""));
                        }

                    }
                }
            }
        }
    }