[lv3] 양과 늑대

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

그래프 탐색에서의 비트마스킹 문제다.

 

문제 특성상 완전 탐색 형태를 이뤄야 하며, 백트래킹을 해도 시간초과다.

(카카오 공식 해설에서는 백트래킹 풀이를 작성했다고 하는데, 이 역시 최악의 경우엔 시간초과라고 한다.)

 

핵심은, 탐색이 가능하다면 탐색 순서는 중요하지 않으므로 비트마스킹을 통해 방문한 정점만 기록하여

중복 탐색 경우의 수를 없얘는 것이다.

e.g. 1 -> 2 -> 3 == 1 -> 3 -> 2  (둘 다 0b111로 기록)

 

문제를 어렵게 풀고 BaaaaaaaarkingDog님의 코드를 참고해서 다시 한 번 배웠다. 그 차이를 기록하려 한다.

https://blog.encrypted.gg/1029

 

초기 통과 코드

class Solution {
    static int L, E, dp[], inf[];
    static boolean adj[][], vst[];
    public int solution(int[] info, int[][] edges) {
        
        L = info.length + 1;
        E = edges.length;
        inf = info;
        
        adj = new boolean[L][L];
        vst = new boolean[L];
        
        for(int i=0; i<E; i++)
            adj[edges[i][0] + 1][edges[i][1] + 1] = true;
        
        dp = new int[1 << L+1];
        dp[1] = 1;
        vst[1] = true;
        
        dfs(1, 0);
        
        int answer = 0;
        for(int sheep : dp)
            answer = Math.max(sheep, answer);
        return answer;
    }
    
    static void dfs(int bit, int wolf) {
        
        for(int i=1; i<L; i++) {
            if((bit & (1 << i - 1)) != 0) {
                for(int j=1; j<L; j++) {
                    if(adj[i][j] && !vst[j]) {
                        int animal = inf[j-1];
                        if(wolf + animal < dp[bit]) {
                            int next = bit | (1 << j - 1);
                            dp[next] = dp[bit] + (animal == 1 ? 0 : 1);
                            vst[j] = true;
                            dfs(next, wolf + animal);
                            vst[j] = false;
                        }
                    }
                }
            }
        }
    }
}

 

수정 코드

import java.util.*;

class Solution {
    
    int answer = 1;
    int I, E;
    int[] l, r, info;
    boolean vst[];
    void solve(int bit) {
        
        if(vst[bit]) return;
        vst[bit] = true;
        
        int total = 0, wolf = 0;
        
        for (int i=0; i<I; i++) {
            if((bit & (1 << i)) != 0) {
                total++;
                wolf += info[i];
            }
        }
        
        if(wolf * 2 >= total) return;
        
        answer = Math.max(answer, total - wolf);
        
        for(int i=0; i<I; i++) {
            // 방문한 정점 전체에서
            if((bit & (1 << i)) != 0) {
                
                // l,f 자식 탐색
                if(l[i] != -1)
                    solve(bit | (1 << l[i]));
                if(r[i] != -1)
                    solve(bit | (1 << r[i]));
            }
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        I = info.length;
        E = edges.length;
        this.info = info;
        l = new int[I];
        r = new int[I];
        vst = new boolean[1 << I];
        
        // 0번 루트 존재 구분
        Arrays.fill(l, -1);
        Arrays.fill(r, -1);
        
        for(int[] edge : edges) {
            int parent = edge[0];
            int child = edge[1];
            
            if(l[parent] == -1)
                l[parent] = child;
            else r[parent] = child;
        }
        
        solve(1);
        
        return answer;
    }
}

 

 

차이점/배운점

 

1 이진 트리의 표현

인접 매트릭스 표현을 위해 [V][V] = V^2 크기의 배열을 선언할 필요가 없었다.

l[V], r[V] = V*2  크기의 배열을 통해 왼/오른쪽 자식만 기록한다. 시간/공간복잡도 모두 더 나은 방법이었다.

 

이는 이진 트리 이며, 상하관계만 표현하면 사실상 자식을 왼쪽에 놓던 오른쪽에 놓던 상관없기 때문에 가능하다.

 

2. 탐색의 표현

나는 매 순간 양과 늑대의 개수를 세어서 가능하다면 양의 수를 dp에 기록했었다.

수정한 코드는 방문 여부만 체크하고 비트 전체개수와 늑대 수를 비교하였다.

문제 특성상 마스킹한 모든 노드 탐색마다 다시 방문해야 했기에, 성능엔 딱히 이점이 없다고 느꼈고 수정 코드가 훨씬 간결했다.

 

3. 비트 마스킹의 표현

문제에서 root는 0번 노드이다. 이를 마스킹 하기위해, i  <<  x = 0을 만족하는 x값을 찾는 방식에 어려움을 느꼈다.

그래서 결국 root를 1번으로 놓기 위해 초기화가 복잡해졌는데, 단순히 비트마스킹에서만 1을 0번 노드로 표시하고 자료구조는 그대로 쓸 수 있었다.

 

그 밖에 코드가 전체적으로 간결해서 많은 걸 배웠다.