📌 문제 설명

양과 늑대 문제 보기

📌 문제 접근

일반적인 DFS?

그냥 막히면 돌아오는 백트래킹을 생각했다. 하지만, 되돌아가서 내가 가진 양과 늑대(상태)를 들고 돌아가야하기 때문에 단순한 백트래킹 DFS로 풀면 안됬다.

순간이동과 최적화

다음에 갈 수 있는 배열을 들고 다니면 된다고 생각했다. 따라서 새로운 노드에 도착하면, 갈 수 있는 노드를 저장한다. 그리고 순간이동 하듯 다른 노드로 가면 되기 때문이다.

그런데 배열을 들고 다니면 효율적이지 못하다고 생각했다. 마침 info 길이가 17? 32비트 정수 이하면 비트마스킹 연습하는게 좋다고 판단하였다. 따라서 최적화 해봤다.

단방향 간선

위로 올라가는 것이 아닌 순간이동을 하기 때문에 양방향 사용 시 또 양과 늑대를 세고 무한루프에 빠지게 된다. 따라서 단방향 내려가는 트리로 문제를 풀어야한다.

📌 내가 작성한 코드

function solution(info, edges) {
    const graph = edges.reduce((acc,cur)=>{
        const [start, end] = cur;
        acc[start].push(end);
        return acc;
    },Array.from({length:info.length},()=>[]));
    
    let answer = 0;
    const dfs = (node,sheep,wolf,nextMask) =>{
        if (info[node]) wolf++;
        else sheep++;
    
        if (wolf>=sheep) return;
        answer = Math.max(sheep,answer); 
        
        let newMask = nextMask & ~(1 << node);
        for (const child of graph[node]) {
            newMask |= (1 << child);
        }
        
        for (let i = 0; i < info.length; i++) {
            if (newMask & (1 << i)) {
                dfs(i, sheep, wolf, newMask);
            }
        }
    }
    dfs(0, 0, 0, 1);
    return answer;
}

📌 시간 복잡도

• 방문 가능한 다음 노드 집합을 매번 복사하며 모든 경우를 DFS로 탐색하므로, 최악의 경우 부분집합/순열 수준으로 분기되어 O(2^N)에 가깝게 증가한다.

📌 참고 링크

• Array.reduce()

• Array.filter()