(코테) 프로그래머스_양과늑대 *dfs + 트리

문제 링크 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=java

 

 

 

풀이

import java.util.*;
class Solution {
    int max =0;
    int len;
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        len=info.length;
        boolean[] visted = new boolean[len];
        List<List<Integer>> list = new ArrayList<>();
        for(int next : info){
            list.add(new ArrayList<>());
        }
        
        // 트리 채우기
        for(int[] next:edges){
            int x=next[0];
            int y=next[1];            
            //단방향
            list.get(x).add(y);            
        }
        visted[0] = true;
        int yang = 0;
        int wolf = 0;
        
        if(info[0]==0) yang ++;
            else wolf++;
        
        
        int[] total = new int[]{yang,wolf};
        List<Integer> nextList = new ArrayList<>(list.get(0)); 
        
        dfs(info,list,visted ,total,nextList);

        return max;
    }
    
    public void dfs(int[] info,List<List<Integer>> list, boolean[] visted ,int[] total,List<Integer> nextList){
        int yang = total[0];
        int wolf = total[1];     
        
        //방문배열 다음꺼 넘길거 복제
           
        //갱신값 확인 양과 늑대가 동일하거나 늑대가 많으면  종료
        if(yang<=wolf) return;         
        max = Math.max(yang,max);
        
        
        //다음 노드 반복  *visted, next리스트 ,양 늑대 갯수  지역 변수로 새로 선언해서 복제해서 사용해서 
        //전체 노드 순회 가능 현재 노드는 방문처리 
        for(int j=0;j<nextList.size();j++){
            int i = nextList.get(j);
            //방문체크 
            if(visted[i]) continue;            
                                    
            //새 방문체크
            boolean[] newVisted = visted.clone();
            newVisted[i]=true;
            List<Integer> newNextList = new ArrayList<>(nextList);            
            newNextList.remove(j); //현재 인덱스는 제외
            
            for(int next : list.get(i)) if(!newVisted[next]) newNextList.add(next);
                
            
        
            int nyang = yang + (info[i]==0 ? 1 : 0);
            int nwolf = wolf + (info[i]==1 ? 1 : 0);
            
            
            
            dfs( info,list,newVisted , new int[]{nyang,nwolf} , newNextList);
        }
                    
        
        
    }
    
}

 

회고

 

문제-해당 문제는 이진 트리로  노드마다 양,늑대가 있고 가장 많은 양을 가져오는 케이스의 양 개수 구하는 문제임

 

최초 접근 - dfs 순회로 완전탐색을 해야한다고 판단은 했음. 하지만 dfs가 기존에 하던 일반 배열에서 도는게 아닌 트리 노드로 구성되기도 하고  이전에 갔던 노드도 방문을 할 수 있는 접해본적 없는 케이스라 코딩에 어려움을 느꼈음.

 

해결방안- dfs 돌때마다 지역스코프로 새로운 배열 객체  양과늑대 , 순회 할 수 있는 노드 리스트,  방문 배열 등 
원본?? 배열들을 clone 해서  다음 dfs로 넘겨 전체 순회를 할 수 있는 방법으로 해결할 수 있었다.