2022 KAKAO BLIND RECRUITMENT - 양과 늑대

[문제링크]

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

코딩테스트 연습 - 양과 늑대

---

[설명]

이 문제도 처음에 풀지 못하였습니다. 다른 사람들의 풀이를 보고 이해한 뒤 DFS로 풀었습니다.

1) childs라는 ArrayList를 만들어 edges를 입력해준다.

2) DFS를 돌린다.

3) 해당 위치의 info가 0일 경우 sheepcount++, 1일 경우 wolfcount++를 해준다.

4) maxSheepCount를 업데이트 해준다.

5) 만약 wolfCount가 더 많다면 return 해준다.

6) nextNodes의 방문 노드들에 childs[node]를 전부 더해준다.

 

 

프로그래머스 2022 KAKAO BLIND RECRUITMENT - 양과 늑대 JAVA풀이

 

import java.util.*;

class Solution {
    public int maxSheepCount;
    public ArrayList<Integer>[] childs;
    
    public int solution(int[] info, int[][] edges) {
        childs = new ArrayList[info.length];
        
        for(int[] link : edges){
            int parent = link[0];
            int child = link[1];
            
            if(childs[parent] == null) {
                childs[parent] = new ArrayList<>();
            }
            childs[parent].add(child);
        }
        List<Integer> nextNodes = new ArrayList<>();
        nextNodes.add(0);
        DFS(0, 0, 0, nextNodes, info);
        
        return maxSheepCount;
    }
    
    public void DFS(int sheepCount, int wolfCount, int node, List nextNodes, int[] info){
        sheepCount += info[node] == 1?0:1;
        wolfCount += info[node];
        maxSheepCount = Math.max(maxSheepCount, sheepCount);
        
        if(sheepCount <= wolfCount) {
            return;
        }
        
        List<Integer> temp = new ArrayList<>();
        temp.addAll(nextNodes);
        
        if(childs[node] != null){
            temp.addAll(childs[node]);
        }
        temp.remove(Integer.valueOf(node));
        
        for(int nextNode : temp){
            DFS(sheepCount, wolfCount, nextNode, temp, info);
        }
    }
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.