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

Ilhwanee·2022년 5월 25일
0

코딩테스트

목록 보기
4/155

문제 보기



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

풀이

  • 이진 트리의 모든 경우의 수를 찾기 위하여 boolean 배열 visited 사용하여 DFS

  • visited를 false로 초기화 하고 0번 노드부터 dfs() 시작
  • 방문 안했으면 true로 바꾸고 양이면 sheepCnt++ 하고 maxSheepCnt와 비교하여 교체, 늑대면 wolfCnt++
  • sheepCntwolfCnt보다 작거나 같으면 잡아 먹으니 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);
            }
        }
    }
}
profile
블로그 이전 -> https://pppp0722.github.io

0개의 댓글