[프로그래머스] 양과 늑대 - 22 카카오 채용 (Java)

이 문제는 좀 문제(?)가 있는 문제라고도 할 수 있다.

시간복잡도적으로 더 효율적인 코드를 알게 되어서 그 내용을 정리해보려고한다.

 

 

문제

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

프로그래머스

---

 

내 풀이

일단, 재귀 + 백트래킹으로 풀 수 있는 문제다.

그렇게 풀어도 통과할 수 있다. 나 또한 그렇게 풀었다.

class Solution {
    int answer = 0;

    public int solution(int[] info, int[][] edges) {
        dfs(0, new boolean[info.length], 0, 0, info, edges);
        return answer;
    }

    private void dfs(int idx, boolean[] visited, int sheep, int wolf, int[] info, int[][] edges) {
        visited[idx] = true;

        if(info[idx] == 0) {
            sheep++;
            answer = Math.max(sheep, answer);
        } else {
            wolf++;
        }

        if(sheep <= wolf) {
            return;
        }

        for (int[] edge : edges) {
            if(visited[edge[0]] && !visited[edge[1]]) {
                boolean[] newVisited = visited.clone();
                dfs(edge[1], newVisited, sheep, wolf, info, edges);
            }
        }
    }
}

그런데, 사실 위 방법은 중복이 많은 재귀이기 때문에 어떤 특정 케이스(info 길이가 최대 길이 17일때)에서는 시간초과가 난다.

그럼에도 카카오가 낸 문제에서는 통과하는 불상사(?)가 있다고 한다. 아마 테스트케이스가 부족한 탓인 것 같다.

심지어 카카오에서 제공한 풀이 마저도 위 방법으로 푼다고 하는데, 그래서 어떤 블로그에서는 이러한 부분이 아쉽다고 언급했다.

 

어떤 노드를 방문한 상태가 재귀를 돌리면서 겹칠 수 있다.

이를 비트마스킹으로 메모이제이션함으로써 특정 상태를 방문했는지 여부를 확인하여 해결하면 된다.

그래서 이 방법으로 더 효율적이게 다시 풀어보았다.

 

 

 

---

더 효율적인 풀이

class Solution {
    int answer = 0;
    boolean[] checked;

    public int solution(int[] info, int[][] edges) {
        checked = new boolean[(int) Math.pow(2, info.length)];
        dfs(0, new boolean[info.length], 0, 0, info, edges, 1);
        return answer;
    }

    private void dfs(int idx, boolean[] visited, int sheep, int wolf, int[] info, int[][] edges, int state) {
        visited[idx] = true;
        checked[state] = true;

        if(info[idx] == 0) {
            sheep++;
            answer = Math.max(sheep, answer);
        } else {
            wolf++;
        }

        if(sheep <= wolf) {
            return;
        }

        for (int[] edge : edges) {
            if(visited[edge[0]] && !visited[edge[1]] && !checked[state | (1<<edge[1])]) {
                boolean[] newVisited = visited.clone();
                dfs(edge[1], newVisited, sheep, wolf, info, edges, state | (1<<edge[1]));
            }
        }
    }
}

노드 개수 n개에 따라 2^n 크기의 배열을 만들어준다.

재귀를 돌리면서 비트마스킹을 이용하여 노드 방문 상태를 갱신해준다.

방문 상태에 따른 체크를 해줌으로써 앞서 말한 테스트케이스도 통과할 수 있게된다.

이로써 훨씬 효율적인 알고리즘을 짤 수 있게 된다.

 

 

 

비트마스킹은 항상 활용하기가 어려운 것 같다.

이 문제에는 비트마스킹을 쓰면 좋겠다 하는 게 잘 안떠오른다.

비트마스킹 문제를 좀 더 풀어보면서 효율적인 코드를 작성할 수 있게 해봐야겠다.