프로그래머스 Java Lv3 양과 늑대

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

해당 문제는 "앞으로 갈 수 있는 노드들"을 포인트로 생각하면 생각보다 쉽게 풀 수 있다.

 

이 문제는 루트 노드에서 출발하여 각 노드를 돌아다니고 양과 늑대를 모으게 된다.

노드는 자유롭게 이동할 수 있으므로 이동 순서에 대한 관리는 필요 없게 된다.

따라서 현재 상태에서 앞으로 갈 수 있는 노드들만 관리하면 된다.

 

현재 노드에서 다른 노드로 이동하는 경우를 생각해보자.

현재 내가 갈 수 있는 노드가 [1, 2, 3] 노드이고, 1번 노드에서 갈 수 있는 노드는 [5, 6, 7] 이라고 가정해보자.

현재 노드에서 1번 노드로 이동한다면, 앞으로 갈 수 있는 노드는 [2, 3, 5, 6, 7] 이다.

 

다음과 같이 노드를 이동하면서 앞으로 갈 수 있는 노드를 관리하면 된다.

 

그리고 Set을 이용하여 효율을 올렸다. Set에는 앞으로 갈 수 있는 노드들의 상태를 저장한다.

앞으로 갈 수 있는 노드들의 상태가 같다는 것은 방문했던 노드들이 같다는 말과 같다.

따라서 현재 노드의 위치는 다르더라도 앞으로 갈 수 있는 노드들이 같다면 같은 상태라고 볼 수 있다.

 

따라서 Set에 앞으로 갈 수 있는 노드들을 저장하여 같은 상태가 중복되는 것을 방지한다.

 

import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Stack;


class Solution {
    
    private static final int SHEEP = 0;
    private static final int WOLF = 1;
    private List<List<Integer>> nodes = new ArrayList<>();
    // 중복 상태 제거를 위해 사용
    private Set<List<Integer>> memory = new HashSet<>();
    
    public int solution(int[] info, int[][] edges) {
        int maxSheepCnt = 0;     
        init(info, edges);
        
        Stack<State> sta = new Stack<>();
        State start = new State(0,0,0, new ArrayList<>(nodes.get(0)));
        sta.push(start);
        memory.add(start.nextNodes);
        while( !sta.isEmpty() ){
            State cur = sta.pop();
            
            if ( info[cur.node] == SHEEP ){
                cur.sheepCnt++;
            } else if ( info[cur.node] == WOLF ){
                cur.wolfCnt++;
            }
            
            //늑대가 양보다 많거나 같은경우, 혹은 탐색할 노드가 없는 경우
            if( cur.wolfMoreThanSheep() || cur.isFinish() ){
                maxSheepCnt = Math.max(maxSheepCnt, cur.sheepCnt);
                continue;
            }
            
            //다음 갈 수 있는 모든 노드로 가본다
            int size = cur.nextNodes.size();
            for( int i = 0 ; i < size ; i++){
                int nextNode = cur.nextNodes.get(i);
                List<Integer> addedNextNodes = nodes.get(nextNode);
                State nextState = cur.nextState(nextNode, addedNextNodes);
                if( memory.contains(nextState.nextNodes) ){
                    continue;    
                } else {
                    sta.push(nextState);
                    memory.add(nextState.nextNodes);
                }
                
            }

        }
        return maxSheepCnt;
    }
    private void init(int[] info, int[][] edges) {
        int size = info.length;
        for(int i = 0 ; i < size ; i++){
            nodes.add(new ArrayList<>());
        }
        for(int[] edge : edges ){
            int node1 = edge[0];
            int node2 = edge[1];
            
            nodes.get(node1).add(node2);
        }
    }
    
    class State {
        int node;
        int sheepCnt;
        int wolfCnt;
        List<Integer> nextNodes = new ArrayList<>();
        
        public State(int node, int sheepCnt, int wolfCnt, List<Integer> nextNodes) {
            this.node = node;
            this.sheepCnt = sheepCnt;
            this.wolfCnt = wolfCnt;
            this.nextNodes = nextNodes;
        }
        
        public boolean wolfMoreThanSheep(){
            return this.wolfCnt >= this.sheepCnt;
        }
        public boolean isFinish(){
            return this.nextNodes.isEmpty();
        }
        public State nextState(int nextNode, List<Integer> addedNodes){
            List<Integer> newNextNodes = new ArrayList<>(this.nextNodes);
            newNextNodes.remove(Integer.valueOf(nextNode));
            for( int addedNode : addedNodes ){
                newNextNodes.add(addedNode);
            }
            return new State(nextNode, this.sheepCnt, this.wolfCnt, newNextNodes);
        }
    }
}