[pro] 프로그래머스 level3 92343 양과 늑대 (Java) - DFS

[문제]

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

프로그래머스

 

[풀이]

완전 탐색 dfs로 풀 수 있다.

주의할 점은, 이미 지났던 노드를 다시 지나서 왼쪽, 오른쪽 경로로 이동할 수 있는데 이를 고려해줄 필요가 없다는 것이다. 이미 지난 노드에서 양이나 늑대를 얻었기 때문에 다시 지나는 경우는 변화하는게 없다. 따라서 그래프 역시 양방향이 아닌 단방향으로만 만들어줬다.

 

 

0에서 1로 이동했다고 가정해보자. 이후 이동할 수 있는 노드는 2, 4, 8 이다. 만약 다시 0을 지나 8로 이동했다고 가정하면 이동할 수 있는 노드는 2, 4, 7, 9 가 된다. 이런식으로 앞으로 갈 수 있는 노드들만 가지고 탐색을 진행해야 한다.

 

+ 추가로 ArrayList.remove() 시 그냥 int 값을 전달하면 index로 알고 arrayOutOfBounds exception이 발생할 수 있다. 따라서 Integer.valueOf()를 통해 wrapper로 감싼 후 전달해야 일치하는 object를 찾아 삭제해주는 것에 주의!

 

[코드]

 

import java.util.*;

class Solution {
    List<List<Integer>> graph;
    List<Integer> next_nodes;
    int ans;
    
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        //각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 
        
        graph = new ArrayList<>();
        next_nodes = new ArrayList<>();
        
        for(int i=0; i<info.length; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<edges.length; i++){
            graph.get(edges[i][0]).add(edges[i][1]);
        }
        
        for(int i=0; i<graph.get(0).size(); i++){
            next_nodes.add(graph.get(0).get(i));
        }
        
        dfs(0, 0, 0, next_nodes, info);
        
        answer = ans;
        
        return answer;
    }
    
    public void dfs(int curr, int s, int w, List<Integer> next_nodes, int[] info){
        if(info[curr]==0){
            //양
            s++;
        }else{ //늑대
            w++;
        }
        
        if(w >= s) return; //늑대가 양이랑 같거나 많아지면 잡아먹힘. 가면 안됨.
        
        ans = Math.max(ans, s);
        
        for(int i=0; i<next_nodes.size(); i++){
            List<Integer> next = new ArrayList<>();
            next.addAll(next_nodes);
            
            //현재 위치 노드 삭제
            next.remove(Integer.valueOf(next_nodes.get(i)));
            
            //현재 노드의 자식 노드 추가
            for(int j=0; j<graph.get(next_nodes.get(i)).size(); j++){
                next.add(graph.get(next_nodes.get(i)).get(j));
            }
            
            dfs(next_nodes.get(i), s, w, next, info);
        }
        
        return;
        
    }
}