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

문제 보기

트리에서 가능한 모든 경우를 찾기 위해서는 갈 수 있는 모든 노드를 대상으로 DFS 하면 된다.

풀이

• 이진 트리의 모든 경우의 수를 찾기 위하여 boolean 배열 visited 사용하여 DFS
  
  
• visited를 false로 초기화 하고 0번 노드부터 dfs() 시작
• 방문 안했으면 true로 바꾸고 양이면 sheepCnt++ 하고 maxSheepCnt와 비교하여 교체, 늑대면 wolfCnt++
• sheepCnt가 wolfCnt보다 작거나 같으면 잡아 먹으니 return
• 반복문을 돌며 부모 노드는 방문 했고 자식 노드는 방문 안한 경우로 다시 dfs() 호출

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);
            }
        }
    }
}