[프로그래머스] 양과 늑대 - JAVA

🔗 문제

프로그래머스

 

 

👨🏻‍💻 풀이 및 코드

• ArrayList<Integer>[] childs = new ArrayList[info.lenght] 를 사용하여 child[parent].add(child); 를 통해 부모 자식 간의 관계를 연결합니다.
• dfs를 통해 갈 수 있는 노드들을 순회하면서, 만약 늑대의 수와 양의 수가 같아진다면 더 이상 진행이 불가하므로 해당 경우의 순회를 종료합니다.
• 아니라면 최종 답 answer를 Max 값으로 갱신합니다.
• 자식 노드들을 추가하여 해당 경로로 다시 dfs 순회합니다.

 

전체 코드

import java.util.*;

class Solution {
    
    int answer;
    int[] info;
    ArrayList<Integer>[] childs;    //연결된 자식 노드
    
    public int solution(int[] info, int[][] edges) {
        this.info = info;
        childs = new ArrayList[info.length];
        for(int i=0; i<info.length; i++) {
            childs[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges) {
            childs[edge[0]].add(edge[1]);
        }
        
        answer = 0;
        List<Integer> list = new ArrayList<>();
	list.add(0);
        dfs(0, 0, 0, list);
        return answer;
    }
    
    void dfs(int idx, int sheepCnt, int wolfCnt, List<Integer> next) {
        if(info[idx]==0) {
            sheepCnt++;
        } else {
            wolfCnt++;
        }
        
        if(wolfCnt >= sheepCnt) return;     //더이상 진행 불가
        answer = Math.max(answer, sheepCnt);
        
        List<Integer> list = new ArrayList<>();
	list.addAll(next);
	// 다음 탐색 목록중 현재 위치제외
	list.remove(Integer.valueOf(idx));
        for (int child : childs[idx]) {
            list.add(child);
        }
        
	// 갈수 있는 모든 Node Dfs
	for (int child : list) {
		dfs(child, sheepCnt, wolfCnt, list);
	}
        
    }
}