[프로그래머스 / Java] 양과 늑대

문제

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

프로그래머스

 

---

 

문제 개요

이 문제는 2진 트리 형태의 초원을 탐험하면서 가능한 많은 양을 모으는 문제다.
트리의 각 노드에는 양 또는 늑대가 한 마리씩 배치되어 있고, 루트 노드(0번)에서 출발하여 노드를 방문할 때마다 그 노드에 있는 동물이 따라오게 된다.

문제의 핵심 조건은 다음과 같다:

• 양과 늑대가 함께 따라오며,
• 늑대의 수가 양의 수 이상이 되는 순간, 모든 양이 잡아먹혀 탐색이 실패하게 된다.
• 이 조건을 지키면서 가능한 많은 양을 수집하는 경로를 탐색해야 한다.

 

 

접근 방법

이 문제는 단순한 DFS나 트리 순회로는 해결할 수 없다. 이유는 다음 탐색 노드가 "현재 위치의 자식"뿐만 아니라, "지금까지 지나온 모든 노드의 자식" 중에서 선택 가능하기 때문이다. 따라서 일반적인 트리 탐색이 아닌, 상태 기반 DFS + 백트래킹을 적용해야 한다.

1. 방문 가능한 노드들을 매 단계마다 리스트로 관리한다.
   즉, 한 노드를 방문한 뒤 그 자식들을 "다음 후보군"으로 추가해두고, 후보군 중 아무 노드나 선택해 DFS를 진행한다.
2. 현재 양과 늑대의 수를 계속 추적하면서, 늑대 수가 양 수 이상이 되는 순간 탐색을 중단한다.
3. 현재까지 모은 양의 최대값을 계속 갱신하며, 그중 가장 큰 값을 정답으로 사용한다.

 

코드

import java.util.*;
class Solution {
    static List<Integer>[] tree;
    static int ans = 0;
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        tree = new ArrayList[info.length];
        
        for(int i=0; i<info.length; i++) tree[i] = new ArrayList<>();
        for(int[] arr : edges) tree[arr[0]].add(arr[1]);
        
        List<Integer> next = new ArrayList<>();
        next.add(0);
        bt(0,0,0, next, info);
                
        return ans;
    }
    
    public void bt(int cur, int sheep, int wolf, List<Integer> next, int[] info) {
        if(info[cur] == 0) {
            sheep++;
        } else {
            wolf++;
        }
        
        if(wolf >= sheep) return;
        ans = Math.max(ans, sheep);
        
        List<Integer> list = new ArrayList<>(next);
        list.remove(Integer.valueOf(cur));
        list.addAll(tree[cur]);
        
        for(int n : list) {
            bt(n, sheep, wolf, list, info);
        }
    }
}