늑대의 개수가 양과 동일해지지 않도록 탐색을 하면서 양을 최대한 많이 챙겨야 하는 문제입니다.
처음엔 BFS를 생각했는데, 왼쪽부터 도는 것과 오른쪽 부터 도는 것의 차이가 생겨서 제대로 된 탐색이 어려웠고,
그리디 알고리즘으로 생각을 전환하였습니다.
양을 만나기 위해 필요한 늑대의 수를 배열에 담고, 오름차순으로 정렬하여 현재 양의 개수 - 1보다 적다면 해당 양을 챙길 수 있다는 가정하에 진행하였으나,
해당 양을 데리러 가는 길에 만나서 내가 데리고 있는 늑대의 수를 체크하기가 어려웠습니다.
다시 생각해보면 해당 양을 만나기 위해 필요한 늑대의 수가 아닌, 늑대의 인덱스를 담아두어 방문처리를 해주면 될 것 같긴 한데, 이렇게 되면 해당 양을 만나러 갈 때 거치게 되는 늑대의 수가 뒤죽박죽 됐고,
늑대를 제거하는 식으로 생각을 해도, 어떤 늑대를 제거하는 것이 가장 그리디한 방법인지 찾기가 어려웠습니다.
똑같이 양을 만나러 갈 때 필요한 늑대의 수가 2마리더라도, 자식이 2개인 늑대노드를 제거하는게 더 이득일지... 다 고려를 해야하는걸까 고민하던차에
이리 생각하고 저리 생각해도 자꾸 막혀 다시 문제를 살펴보니 info 개수가 17개더군요..
눈치를 챘어야 하는데... 제발 문제를 풀기 전에 문제 조건을 다시 한 번 봐야겠다는 다짐을 하게 되는 문제였습니다.
브루트포스라는 걸 알았으니, 이제 늑대 수와 양 수를 저장해두어 분기마다 갈 수 있는 모든 노드에 대해 완전탐색을 해주면 됩니다.
import java.util.*;
class Solution {
static List<List<Integer>> adj = new ArrayList<>();
static boolean[] wolf;
static int ans;
public int solution(int[] info, int[][] edges) {
int answer = 0;
wolf = new boolean[info.length];
for(int i=0; i<info.length; i++){
adj.add(new ArrayList<>());
if(info[i] == 1){
wolf[i] = true;
}
}
for(int[] edge : edges){
adj.get(edge[0]).add(edge[1]);
}
dfs(0, new ArrayList<>(), 0, 1, new boolean[info.length]);
return ans;
}
private static void dfs(int i, List<Integer> lst, int wolfCnt, int sheepCnt, boolean[] visited){
ans = Math.max(ans, sheepCnt);
List<Integer> arr = new ArrayList<>();
for(int num : adj.get(i)){
if(!visited[num]){
arr.add(num);
}
}
for(int num : lst){
if(!visited[num]){
arr.add(num);
}
}
for(int node : arr){
if(!wolf[node] && !visited[node]){
visited[node] = true;
dfs(node, arr, wolfCnt, sheepCnt+1, visited);
visited[node] = false;
}
if(wolf[node] && !visited[node] && sheepCnt - 1 > wolfCnt){
visited[node] = true;
dfs(node, arr, wolfCnt+1, sheepCnt, visited);
visited[node] = false;
}
}
}
}