99클럽 코테 스터디 8일차 TIL 백트래킹(양과 늑대)

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

프로그래머스

 

사용 알고리즘

DFS, 백트래킹

 

아이디어

1. 리스트에 현 노드의 자식 노드를 탐색해 나감.

2. 양 <= 늑대면 dfs 타지 않고, 자식 노드를 DFS에 태우지 않음.

3.  양 > 늑대를 만족하는 경우를 우선 탐색하면서 이전에 탐색하지 못했던 노드 재탐색.

4. 최대 양의 수 갱신

 

제출코드

import java.util.*;

class Solution {
    
    static int len;
    static int maxAns;
    static List<Integer>[] list;
    
    public static void dfs(int sheep, int wolf, List<Integer> node, int[] info){
        
        maxAns = Math.max(maxAns, sheep);
            
        for(int i=0; i<node.size(); i++){
            int x = node.get(i);
            
            // 다음 탐색 가능한 노드들 - 자식 노드
            List<Integer> next = new ArrayList<>(node);
            next.remove(i);             // 현 노드는 제거
            next.addAll(list[x]);       // 현 노드의 자식 노드 추가
            
            if(info[x] == 0) {
                dfs(sheep+1, wolf, next, info);            // 양
            }
            else if(sheep > wolf + 1) {
                dfs(sheep, wolf+1, next, info);   // 늑대면서 양보다 적을 때
            }
        }
        
    }
    
    public int solution(int[] info, int[][] edges) {
        
        len = info.length;
        
        list = new ArrayList[len];
        for(int i=0; i<len; i++){
            list[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges){
            list[edge[0]].add(edge[1]);
        }
        
        // 초기 탐색 가능한 노드
        List<Integer> node = new ArrayList<>();
        node.add(0);
        
        dfs(0, 0, node, info);
        
        return maxAns;
    }
}