[프로그래머스] 양과 늑대 (JAVA 풀이)

 

문제 접근

 

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

프로그래머스

 

처음에는 문제를 보고 든 생각은 최대 17개의 노드이므로 모든 경우를 전부 따져보면 될 것 같았음

하지만, 재귀 구현 과정에서 자꾸 무한루프가 발생해서 힘들었던 문제

 

문제 풀이

 

이 문제의 핵심 포인트는 현재 노드 기반이 아니라 현재 상태(양, 늑대, 다음 방문 가능 노드 목록)으로 탐색을 진행해야된다는 것임

 

=> 즉, 지금까지 방문한 모든 노드에 연결된 모든 자식 노드들 중에서 하나를 골라 다음으로 방문해야 무한 루프없이 문제를 제대로 풀 수 있음

 

우선, 양의 최댓값을 저장하는 max와 각 노드별 양과 늑대 여부를 나타내는 info를 전역 변수 infoArr로 선언해줬음

그리고 각 노드별로 다음에 이동할 수 있는 (연결된) 자식 노드 번호를 저장해두기 위해 List<List<Integer>>를 선언해줬음

 

=> 이 때 인덱스 에러를 방지하기위해 각 노드별로 ArrayList를 먼저 초기화해주고 각 노드별로 자식 노드 번호를 저장해야함

 

이렇게 List까지 완성했다면 재귀를 통해 정답을 구하면되는데 현재 상태에서 양의 개수, 늑대의 개수, 다음 이동할 수 있는 노드들의 List를 매개변수로 받는 dfs 함수를 선언해줬음

 

=> 첫 루트 노드는 무조건 0번이고 양 1마리가 존재하므로 dfs를 처음 호출할 때는 양 1마리, 늑대 0마리, tree.get(0)을 통해 0번 노드와 연결된 자식들을 넘겨줘야함

 

dfs함수 내부에서는 Math.max 함수를 통해 현재 상태에서 양의 개수가 max에 저장된 최댓값보다 많다면 max를 현재 양의 개수로 갱신시켜줌

=> 왜냐하면 무조건 트리  전체를 탐색한 후의 양의 개수를 구하는게 아니기 때문에 양이 최대가 되는 순간이 탐색 중간에 있으면 해당 노드에서 멈춰줌을 표현하기 위해서

 

이후 매개변수로 전달받은 현재 상태에서 이동가능한 노드들로 dfs함수를 전개하는데 다음 이동할 노드의 infoArr 정보를 통해 0이면 양의 개수를, 1이면 늑대의 개수를 늘려주고 늑대가 양의 개수와 동일하거나 커지면 그 뒤의 탐색은 의미가 없어지므로 continue처리해줌

 

=> 늑대가 잡아먹으면 그 뒤의 어떤 노드를 방문해도 무조건 늑대와 양의 개수가 같아지거나 늑대 개수가 늘어나므로 최대의 양 개수가 나올 수 없음

 

만약 다음 노드로 이동이 가능하다면 (양이 늑대보다 많다면) 다음 방문할 노드는 앞으로 방문할 노드의 List에서 remove해주고 다음 방문할 노드에서 또 다음으로 방문할 수 있는 자식들의 경우를 List에 추가해줌

 

=> 이제 이렇게 다음 노드로 이동한 상태로 갱신된 양의 개수, 늑대의 개수, 이동 가능한 노드 List를 담아서 dfs를 재귀 호출시켜주면됨

 

dfs함수가 종료되면 max에는 모든 경우를 탐색하며 양의 개수가 최대였던 시점의 양의 개수가 담겨져있으므로 이를 return하면 끝남

 

전체 코드

 

import java.util.*;

class Solution {
    
    int max = -1;
    int[] infoArr;
    
    List<List<Integer>> tree = new ArrayList<>();
    
    void dfs(int sheep, int wolf, List<Integer> nextNodes) {
        
        // 현재 양의 개수가 max보다 많다면 갱신
        max = Math.max(max, sheep);
        
        // 다음에 이동 가능한 (자식)노드들로 전개
        for(int i = 0; i < nextNodes.size(); i++) {
            
            int nextNode = nextNodes.get(i);
            int newSheep = sheep;
            int newWolf = wolf;
            
            
            // 다음 노드가 0이면 양
            if(infoArr[nextNode] == 0) {
                newSheep++;
            } else { // 1이면 늑대
                newWolf++;
            }
            
            // wolf가 잡아먹으면 그 뒤의 탐색은 의미 X
            if(newWolf >= newSheep) continue;
            
            List<Integer> newNextNodes = new ArrayList<>(nextNodes);
            
            // 다음 방문할 노드(현재 i가 가리키는 노드)는 앞으로 방문할 노드에서 제거해줌
            newNextNodes.remove(i);
            
            // 다음 방문할 노드(현재 i가 가리키는 노드)에서 방문할 자식들을 앞으로 방문할 노드에 추가해줌
            newNextNodes.addAll(tree.get(nextNode));
            
            dfs(newSheep, newWolf, newNextNodes);
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        
        infoArr = info;
        
        // 각 node별로 ArrayList 초기화
        for(int i = 0; i < info.length; i++) {
            tree.add(new ArrayList<>());
        }
        
        // 각 node별로 갈 수 있는 자식 node 번호를 저장해둠
        for(int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
        }
        
        // 루트 노드(양 1마리) 부터 시작
        dfs(1, 0, tree.get(0)); 
        
        return max;
    }
}