프로그래머스 양과 늑대 (자바)

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

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

---

문제 사고하기

1. 일반적인 dfs와 같지 않다.

2. 양과 늑대의 수과 같아지거나, 늑대의 수가 더많다면, 변형된 dfs를 수행하다가 종료한다.

3. 양의 수의 최댓값을 갱신해가면서 최종적인 최댓값을 return한다.

-> 어떻게 문제를 풀이할까? 

 - 루트 노드부터 시작하여 방문할 수 있는 노드를 계속 기억해주어야 한다. 

- 방문한 노드는 방문할 수 있는 노드리스트에서 제거해준다.

 

소스코드

import java.util.*;
class Solution {
    static int maxSheep;
    static List<List<Integer>> graph = new ArrayList<>();
    static int [] sInfo;
    public int solution(int[] info, int[][] edges) {
        sInfo = info;
        for(int i =0 ; i<info.length; i++){
            graph.add(new ArrayList<>());
        }// graph 초기화 해주기
        for(int i=0; i<edges.length; i++){
            int parent = edges[i][0];
            int child = edges[i][1];
            graph.get(parent).add(child);
        }
        List<Integer> par = new ArrayList<>();
        par.add(0);
        dfs(0, par, 0, 0);
    
        return maxSheep;
    }
    static void dfs(int node, List<Integer> nextList, int sheep, int wolf){
        if(sInfo[node]==0) sheep++; //dfs로 들어온 현재 노드가 양이라면
        else wolf++; //늑대라면
        if(sheep<=wolf) return; //양과 늑대의 수가 같거나 늑대가 더많다면
        
        maxSheep= Math.max(maxSheep, sheep);
        //다음에 방문해야 할 리스트 초기화 하기
        List<Integer> next = new ArrayList<>(nextList);
            if(!graph.get(node).isEmpty()){
                next.addAll(graph.get(node));
            }
        next.remove(Integer.valueOf(node)); // 그냥 노드값 넣으면 안됨 메모리 초과
        for(int nextNode: next){
            dfs(nextNode, next, sheep, wolf);
        }
    }
}

 

느낀점: IDE의 도움없이 문제를 풀이할 때, 항상 한번에 성공한 케이스가 없는 것 같다. 꾸준한 학습만이 답이다.