양과 늑대(프로그래머스) JAVA

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

프로그래머스

 

문제 설명

• 각 노드에 가면 그 위치에 있는 양이나 늑대가 따라옴
• 양의 수가 늑대의 수가 같거나 늑대의 수가 더 많아지면 늑대가 양을 다 잡아먹음
• 최대 한 많은 수의 양을 모아서 다시 루트 노드로 돌아오는 방법을 구해라!!

제일 처음 0을 갔다가 1을 갔다가 4를가면 양이 2마리 늑대가 1마리를 가지고 있다. 그리고 2 ,3 ,6 으로 가면 늑대가 2마리 양이 2마리이므로 접근이 불가능하다. 그러므로 8로 가야한다.

8로 간 후 7,9 로가 양을 2마리 얻고 4, 6 을 들린 후 5로가면 최대 양 5마리를 얻을 수 있다!!

 

문제에 대한 아이디어

이 문제는 일반 트리 순회 문제랑 다르다. 한쪽 으로만 가면 안되고 양쪽으로 움직여야 한다. 그러므로 다음 노드 위치를 잘 선정해줘야 한다. 예를 들어 0 -> 1 을 갔다가 2,4,3,6으로 접근이 불가능한 것을 보고 8로 갈 수 있어야 한다. 그리고 7, 9를 간 다음에 10,11로 가지 않고 2, 4, 3, 6으로 접근할 수 있어야 한다. 이 문제를 어떻게 해결할 수 있을까? 고민하다가 다음 방문해야 할 노드 위치를 계속 List에 저장하면 될 것 같다고 생각했다.

 

다음 노드 위치 저장

• 처음 시작 할 때, 다음 노드 위치에는 0번이 들어 간다.
• 그 후, 0번의 자식들 1, 8이 다음 노드 List에 들어간다.
• 1번에 들린 후 다음 노드 위치에는 그의 자식인 2,4가 들어간다. 현재 List에는 2,4,8이 존재한다.
• 그 후 다음 갈 수 있는 노드를 모두 방문해 보는 것이다. 
• 2,4번을 모두 들린 후에 안되는 것을 확인하고 8번에 들린다. 8번 node로 갔을 때, 다음에 방문해야할 노드 List에 저장 되어 있는 것은 2,4,8번이다!!

이렇게 모두 방문한다는 것은 1번에서 2번방문하고 1번에서 4번 방문하고 1번에 8번 방문하는 3개의 케이스로 모두 방문해 보는 것이다. 이렇게 하면 각각 모든 case를 조사해볼 수 있다.

 

구현

• Main

class Solution {
    ArrayList<Integer> ar[];
    int count;
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        ar = new ArrayList[info.length];
        for(int i =0; i<info.length; ++i){
            ar[i] = new ArrayList<>();
        }
        for(int i = 0; i< edges.length; ++i){
            int u = edges[i][0]; 
            int v = edges[i][1];
            ar[u].add(v);
        }
        ArrayList<Integer> res = new ArrayList<>(); // 방문해야할 노드
        res.add(0);
        dfs(0,0,0, info, res);
        answer =count;
        return answer;
    }

• dfs

public void dfs(int idx, int sheepCount, int wolfCount, int[] info, ArrayList<Integer> nextVisited){
        //0일 경우 양, 1일 경우 늑대
        if(info[idx] == 0) ++sheepCount;
        else ++wolfCount;
        //양보다 늑대가 같거나 많아지면 return
        if(sheepCount <= wolfCount) return;
        count = Math.max(sheepCount, count);
        ArrayList<Integer> temp = new ArrayList<>();
        //현재 방문해야할 노드 temp에 저장
        temp.addAll(nextVisited);
        //현제 index 제거
        temp.remove(Integer.valueOf(idx));
        //지금 index에 자식이 있으면 temp에 모두 저장
        if(ar[idx].size() != 0){
            for(Integer a : ar[idx]){
                temp.add(a);
            }
        }
        //방문할 수 있는 노드 모두 방문해보기
        for(Integer te : temp){
            dfs(te,sheepCount,wolfCount,info,temp);
        }
        
    }
}