트리에서 가능한 모든 경우를 찾기 위해서는 갈 수 있는 모든 노드를 대상으로 DFS 하면 된다.
visited
사용하여 DFSvisited
를 false로 초기화 하고 0번 노드부터 dfs()
시작sheepCnt
++ 하고 maxSheepCnt
와 비교하여 교체, 늑대면 wolfCnt
++sheepCnt
가 wolfCnt
보다 작거나 같으면 잡아 먹으니 returndfs()
호출class Solution {
int[] gInfo;
int[][] gEdges;
int maxSheepCnt = 0;
public int solution(int[] info, int[][] edges) {
gInfo = info;
gEdges = edges;
boolean[] initVisited = new boolean[info.length];
dfs(0, initVisited, 0, 0);
return maxSheepCnt;
}
public void dfs(int idx, boolean[] visited, int sheepCnt, int wolfCnt) {
visited[idx] = true;
if (gInfo[idx] == 0) {
sheepCnt++;
if (sheepCnt > maxSheepCnt) {
maxSheepCnt = sheepCnt;
}
} else {
wolfCnt++;
}
if (sheepCnt <= wolfCnt) {
return;
}
for (int[] edge : gEdges) {
if (visited[edge[0]] && !visited[edge[1]]) {
boolean[] nextVisited = new boolean[visited.length];
for (int i = 0; i < visited.length; i++) {
nextVisited[i] = visited[i];
}
dfs(edge[1], nextVisited, sheepCnt, wolfCnt);
}
}
}
}