카카오 - 양과 늑대

코드

class Solution {

    boolean[] visited;
    int answer = 1;
    int[] info;
    Map<Integer,List<Integer>> map;

    public int solution(int[] infos, int[][] edges) {

        visited = new boolean[infos.length];
        info = infos;
        map = new HashMap<>();

        for (int i=0;i<infos.length;i++) {
            map.put(i, new ArrayList<>());
        }

        for (int[] arr : edges) {
            map.get(arr[0]).add(arr[1]);
        }



        visited[0] = true;
        dfs(1, 0, new ArrayList<>(map.get(0)));

        return answer;
    }

    void dfs(int sheep, int wolf, List<Integer> list) {

        for (int i =0; i< list.size();i++ ) {

            int next = list.get(i);

            if (visited[next])
                continue;

            visited[next] = true;
            ArrayList<Integer> list1 = new ArrayList<>(list);
            list1.addAll(map.get(next));
            //양
            if (info[next] == 0) {
                answer = Math.max(answer, sheep + 1);
                dfs(sheep + 1, wolf, list1);
            }
            //늑대
            if (wolf + 1 < sheep) {
                dfs(sheep, wolf + 1, new ArrayList<>(list1));
            }
            visited[next] = false;
        }
    }


}

해설

🥳dfs + 완전탐색으로 풀은 문제이다. 먼저 map에 해당 노드들의 관계를 저장해주고 dfs를 돌린다.
dfs를 돌릴때 list에는 다음 갈 수 있는 노드들의 값들을 저장해 주었는데 여기서 visited 배열을 통해 이미 방문한 곳은 다시 방문하지 않도록 하였다(이 부분을 고치면 메모리 사용량을 줄일 수 있다).

이 후 양이라면 다음 dfs를 돌리는데 이때 최대값을 갱신해준다. 만약 늑대라면 양이 다 잡아먹히지는 않는지 확인을 하고 괜찮다면 다음으로 보내준다. 이렇게 dfs를 돌리면 정답이 나오게 된다.

코드를 보면 개선의 여지가 많은 코드이다.
아래는 다른 분의 코드를 참고하여 다시 고친 코드입니다.

import java.util.*;

class Solution {
    
   int answer = 1;
    int[] info;
    Map<Integer, List<Integer>> map;

    public int solution(int[] infos, int[][] edges) {
        
        info = infos;
        map = new HashMap<>();
        for (int i = 0; i < infos.length; i++) {
            map.put(i, new ArrayList<>());
        }

        for (int[] arr : edges) {
            map.get(arr[0]).add(arr[1]);
        }
        
        dfs(1, 0, new HashSet<>(map.get(0)));

        return answer;
    }

    void dfs(int sheep, int wolf, HashSet<Integer> set) {
        answer = Math.max(answer, sheep);
        if (sheep == wolf)
            return;

        for (int next : set) {
            HashSet<Integer> nextSet = new HashSet<>(set);
            nextSet.addAll(map.get(next));
            nextSet.remove(next);
            if (info[next] == 0) {
                dfs(sheep + 1, wolf, nextSet);
            } else {
                dfs(sheep, wolf + 1, nextSet);
            }
        }
    }
}

Set을 사용하는게 더 깔끔하고 더 빨라진것을 볼 수 있습니다.

출처 : 프로그래머스 - 양과 늑대