(JAVA) 양과 늑대

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

풀이

class Solution {
    int[] gInfo; // DFS에서 사용할 노드의 정보
    int[][] gEdges; // DFS에서 사용할 간선의 정보
    int maxValue = 0;
    
    public int solution(int[] info, int[][] edges) {
        gInfo = info;
        gEdges = edges;
        boolean[] isVisited = new boolean[info.length]; // 노드에 방문하였는지 체크하는 배열
        dfs(isVisited, 0, 0, 0); // DFS로 트리 순회
        return maxValue;
    } 
    
    public void dfs(boolean[] isVisited, int idx, int sheep, int wolf){
        isVisited[idx] = true; // 방문 표시
        if (gInfo[idx] == 0) { // 노드가 양이 위치한 노드라면
            sheep++; // 양을 카운트업
            if(sheep > maxValue) maxValue = sheep; // 현재 양의 수가 최대값을 넘어섰다면 최대값 업데이트
        }
        else wolf++; // 늑대가 위치한 노드라면 늑대를 카운트업
        
        if (sheep <= wolf) return; // 늑대가 더 많아지면 DFS 종료
        
        for (int[] edge : gEdges) { 
            if (isVisited[edge[0]] && !isVisited[edge[1]]) { // 간선에서 부모만 방문한 상태라면
            	boolean[] nextVisited = new boolean[isVisited.length]; // 다음 DFS에서 사용할 방문 여부 체크 배열 선언
            	for (int i = 0; i < isVisited.length; i++) { // 현재 방문 내역 복사
                	nextVisited[i] = isVisited[i];
            	}
                dfs(nextVisited, edge[1], sheep, wolf); // 다시 DFS
            }
        }
    }
}