프로그래머스 - 양과 늑대

양과 늑대 : https://programmers.co.kr/learn/courses/30/lessons/92343

---

Problem

---

Solve

특별한 알고리즘을 사용하지 않고 재귀함수을 이용하여 구현하였다.
처음에는 Node 클래스로 양과 늑대의 갯수가 동일해지면 부모노드로 돌아가 비트마스킹을 이용한 state로 다른 노드를 방문하는 식으로 구현했지만 오버플로우로 인해 다른 분의 풀이를 참고했다.

문제 풀이는 아래와 같다.

1. 클래스 인스턴스를 사용하지 않고 각 노드에 자식 노드를 저장하는 List로 초기화
2. 노드를 방문하는 재귀함수에 양의 개수(sheepCount), 늑대의 개수(wolfCount), 방문할 노드(nextNode), 각 노드의 동물 종류(info)를 argument로 놓는다.
3. 재귀함수
   • 양의 개수와 늑대의 개수가 동일하면 return
   • 방문할 노드 복사
   • 현재 노드의 자식 노드가 존재한다면 복사한 방문할 노드에 추가
   • 복사한 방문할 노드로 재귀함수 호출

이렇게 하면 양의 개수와 늑대의 개수가 동일할 때 이전 함수에서 다음 방문할 노드에서 양의 개수나 늑대의 개수를 갱신하여 다시 새로운 양의 개수와 늑대의 개수를 가져와 비교할수 있게 된다.(양의 개수 == 늑대의 개수의 조건으로 인해 방문할 노드에서 해당 노드가 제거가 되지 않아 개수가 갱신되고 다시 접근 할 수 있다.)

---

Code

import java.util.*;
class Solution {
    List<Integer>[] relation;
    int answer=0;
    public int solution(int[] info, int[][] edges) {
    	//각 노드의 자식 노드를 저장할 리스트
        relation = new ArrayList[info.length];
        
        for(int[] edge : edges){
            int parents = edge[0];
            int child = edge[1];
            
            if(relation[parents] == null){
                relation[parents] = new ArrayList<>();
            }
            relation[parents].add(child);
        }
        
        answer = 0;
        countSheep(0, 0, 0, new ArrayList<>(), info);
        
        return answer;
    }
    
    //node : 현재노드, sheepCount : 양의 개수, wolfCount : 늑대의 개수, nextNode : 방문할 노드, info : 각 노드의 종
    void countSheep(int node, int sheepCount, int wolfCount, List<Integer> nextNode, int[] info){
        sheepCount += info[node] ^ 1;
        wolfCount += info[node];
        
        answer = Math.max(answer, sheepCount);
        
        //늑대의 개수가 양의 개수와 같거나 크다면 해당 함수 무시
        if(wolfCount>=sheepCount) return;
        
        //방문할 노드 복사
        List<Integer> copyNextNode = new ArrayList<>();
        copyNextNode.addAll(nextNode);
        
        //방문할 노드에서 현재 노드 제거
        copyNextNode.remove(Integer.valueOf(node));
        
        //현재 노드에 자식 노드가 있다면 방문할 노드에 추가
        if(relation[node] != null){
            for(int child : relation[node]){
                copyNextNode.add(child);
            }
        }
        
        //방문할 노드에 갱신된 양의 개수와 늑대의 개수, 방문할 노드를 가지고 재귀함수 호출
        //만약 각 개수가 동일하다면 호출한 함수는 무시되지만 방문할 노드에서는 삭제되지 않는댜. 
        //그렇기 때문에 다음 방문할 노드에서 각 개수가 갱신되고 다시 무시된 노드에 방문하여 위의 프로세스를 반복
        for(int next : copyNextNode){
            countSheep(next, sheepCount, wolfCount, copyNextNode, info);
        }
    }
}

---

Result

---

Reference

https://velog.io/@hengzizng/Programmers-92343