[프로그래머스] 양과 늑대 (java) - DFS //2022 kakao blind recruitment

순위 182위

점수 1,837점

해결한 문제 466개

 

java 언어로 양과 늑대를 풀기 위해서는

가장 간단히 생각나는게 DFS 문제풀이 인데,

어떻게 접근해야 할지 굉장히 고민을 했다.

---

문제 설명

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

프로그래머스

 

---

문제 풀이

이 문제를 풀기 위해서는 DFS의 재귀 호출 방식을 알아야 하는데, 모든 부분을 완전탐색해야지만 풀 수 있다.

1. 제일 처음에 0번 ROOT를 기준으로 DFS로 전체 탐색을 하다가 늑대가 양보다 많아지면 return 한다.

2. 부모 노드는 방문 했지만 자식 노드에 방문을 하지 않았다면 새로운 visit 배열을 만들어서 다시 탐색할 수 있도록 한다. 여기서 중요한 포인트인데, 재귀로 돌아왔을 때, "지금" 자식을 방문할 수 없다면 나중에는 방문가능할 수도 있으니 새로운 visit배열을 만들어서 써야 한다는 점이다.

 

 

import java.util.Arrays;

public class Result3 {
    public static void main(String[] args) {
        System.out.println(solution(new int[]{0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0},
                new int[][] {{0, 1},{0, 2},{1, 3},{1, 4},{2, 5},{2, 6},{3, 7},{4, 8},{6, 9},{9, 10}}));
        System.out.println(solution(new int[]{0,0,1,1,1,0,1,0,1,0,1,1},
                new int[][]{{0,1},{1,2},{1,4},{0,8},{8,7},{9,10},{9,11},{4,3},{6,5},{4,6},{8,9}}));
    }
    static int solution(int[] info, int[][] edges) {
        //1.0은 양, 1은 늑대를 의미합니다.
        //2.info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
        boolean visit[] = new boolean[info.length];
        int sheep = 0;
        int wolf = 0;
        max = 0;
        dfs(visit, 0, info, edges, sheep, wolf);
        return max;
    }

    static int max;
    static void dfs(boolean[] visit, int root, int[] info, int[][] edges, int sheep, int wolf){


        visit[root] = true;
        if(info[root] == 0){
            sheep++;
            if(sheep > max){
                max = sheep;
            }
        }else{
            wolf++;
        }
        if(sheep <= wolf){
            return;
        }
        for(int[] edge: edges){
            int x = edge[0];
            int y = edge[1];
            if(visit[x] && !visit[y]) {
                boolean[] next = new boolean[visit.length];
                for (int i = 0; i < visit.length; i++) {
                    next[i] = visit[i];
                }
                dfs(next,y, info, edges, sheep, wolf);
            }
        }
    }
}