[프로그래머스 Lv3][자바] 양과 늑대

❓문제설명

양과 늑대

프로그래머스

 

---

🔍문제해석

어떤걸 풀어야 할까?

• 이진 트리가 주어지고, 각 지점 마다 양 또는 늑대가 있다.
• 각 지점을 들리면 양 또는 늑대의 수가 더해진다.
• 만약 늑대의 수가 양과 같거나 커진다면 모든 양은 늑대한테 잡하먹힌다.
• 이럴때 최대한 많이 모을 수 있는 양의 수를 구하라.

---

🧐문제풀이

• 문제 풀이 구상

처음에는 단순한 dfs문제라고 생각하고 문제를 풀었으나 계속 내가 도출한 값과 정답이 맞지 않았다.

무슨 문제일까 하고 지문을 자세히 보니, 글쎄 이동을 할때 현재 지점의 하위로만 갈 수 있는게 아니라 아예 다른 노드로도 점프를 할 수 있는 것이었다.

 

이렇게 트리가 주어져있을때의 이동경로는 아래와 같았다.

노드	양의 수	늑대의 수
0	1	0
1	2	0
8	2	1
7	3	1
9	4	1
4	4	2
6	4	3
5	5	3

0-1-8-7-9 까지 진행했다가 10,11을 바로 들리면 늑대의 수가 더 많아지기 때문에

갑자기 4로 건너간다.

멘붕을 하던 중 나와 비슷한 고민을 하셨던 블로그 글을 발견.

해당 글을 참고하여 문제를 풀었다.

https://lympsw12.tistory.com/m/entry/%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JAVA

깊이탐색을 하면서 이동 갈 수 있는 노드 리스트를 데리고 다닌다.이 이동 리스트는 현재 노드에서만 갈 수 있는 목록이 아니라, 이동 오기 전에 갈 수 있었던 가능성이 있는 노드라면 모두 들어가있다.그러다가 늑대가 수가 더 많아지면 return 한다.

• 알고리즘 선택

모든 노드를 들려야했기 때문에 dfs를 선택했다.

---

！제출코드

1. tree에 인접리스트를 만들어준다.
2. 이동 가능한 노드 리스트를 만들어준다.
3. 0이면 양++, 1이면 늑대++
4. 늑대의 수가 양과 같거나 크면, 더 이상 진행할 필요 없으니 return
5. 탐색 중인 양의 수와 변수에 담겨있는 양의 수를 비교했을때 더 큰걸 변수에 담아준다.
6. 앞으로 방문할, 이동가능한 노드들을 담을 리스트 생성
7. 이전 탐색에서 넘어온 노드들을 모두 넣어준다.
8. 현재 노드는 방문했으니 제거, Integer.valueOf(node)로 인자값을 Object로 넘겨줘야 그 Value에 맞는 항목이 삭제된다. 그렇지 않으면 인덱스에 해당되는 항목이 제거되어 오답이 나올 수 있다.
9. 하위 노드도 모두 담는다.
10. 리스트에 있는 노드들에 대한 방문 진행

import java.util.*;

class Solution {
   
    static int[] infoArray;
    static List<List<Integer>> tree;
    static int maxSheep = Integer.MIN_VALUE;
    
  public static int solution(int[] info, int[][] edges) {
  
        infoArray = info;
        tree = new ArrayList<>();
        // (1)
        for (int i = 0; i < info.length; i++) tree.add(new ArrayList<>());
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
        }
        
        // (2)
        ArrayList<Integer> nextVisited = new ArrayList<>();
        
        nextVisited.add(0);
        dfs(0, 0, 0, nextVisited);
        int answer = maxSheep;
        return answer;
    }

    static void dfs(int node, int sheepCount, int wolfCount, ArrayList<Integer> nextVisited) {

        // (3)
        if (infoArray[node] == 0) {
            sheepCount++;
        } else {
            wolfCount++;
        }
        // (4)
        if (sheepCount <= wolfCount) {
            return;
        }
        // (5)
        maxSheep = Math.max(maxSheep, sheepCount);

        // (6) 현재 지점에서 방문 가능할 노드 리스트에 저장
        ArrayList<Integer> temp = new ArrayList<>();
        // (7) 넘어온 리스트는 모두 저장
        temp.addAll(nextVisited);
        // (8) 현재 노드 삭제
        temp.remove(Integer.valueOf(node));
        // (9) 현재 노드 하위에 자식이 있으면 temp에 저장
        for (int nextNode : tree.get(node)) {
           temp.add(nextNode);
        }
        // (10) temp에 담긴 노드 모두 방문
        for (int nextNode : temp) {
            dfs(nextNode, sheepCount, wolfCount, temp);
        }
    }
}