[JS] 프로그래머스 양과 늑대

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

프로그래머스

 

해당 문제는 우리가 알고 있는 bfs/dfs 문제와 달리 방문한 노드를 또 방문할 수 있었다.

따라서 이 부분을 어떻게 고려할까 고민을 많이 했다.

 

정답은 후보 노드 배열을 생성하는 것이었다.

후보 노드 배열을 백트래킹으로 만들어서 관리하는 것도 시도해 보았지만 실패했다.

(js는 shift()를 사용하면 시간복잡도가 O(n)이 나오기 때문에 head를 사용해야 하고 head 관리가 복잡해진다. 등등)

그나마 다행인 것은 노드의 최대 수가 17개이므로 후보 노드 배열을 매번 생성하는 경우에도 공간복잡도를 관리할 수 있다는 것이었다.

 

결론적으로

1. 먼저 주어진 간선들을 연결리스트로 생성한다.

2. dfs 함수를 만든다. (매개변수 : 현재 노드, 양의 수, 늑대 수, 후보 배열)

3. 현재 노드가 양인지 늑대인지 파악하고 답을 갱신한다. (종료 조건 : 양의 수 <= 늑대 수)

4. 새로운 후보 배열을 만들어서 현재 노드와 연결된 노드를 집어 넣는다.

5. 새로운 후보 배열을 돌면서 dfs(다음 노드, 갱신된 양의 수, 갱신된 늑대 수, 다음 노드를 제외한 후보 배열) 실행한다.

6. dfs가 끝난 후에 답을 반환한다.

 

아래는 코드이다.

(그 다음으로 2^17은 131072이므로 비트마스킹으로도 풀어봐야겠다. 공간복잡도가 좋아보인다.)

 

/*
연결리스트
visited 필요 없음(갔던 노드 또 가도 되기 때문에) 대신에 후보 노드 배열 필요.
2^17 = 131072 -> 비트마스킹 가능 -> visited돌기?
순서가 중요하다

후보 노드 백트래킹 구현(시도해보았지만 실패)
후보 노드 인자로 넘기기
*/

function solution(info, edges) {
    const n = info.length;
    // 최대 양을 저장할 수 있는 변수 초기화
    let answer = 0;
    
    // 연결리스트 생성 단방향 간선 (사이클 없는 트리)
    const graph = Array.from({length : n}, () => []);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
    }
    
    // 시작 노드, 늑대 수, 양의 수, 후보 배열
    const dfs = (node, w, s, candidates) => {
        // 1) 현재 노드 확인 -> 늑대 수, 양의 수 갱신
        const nw = info[node] === 1 ? w + 1 : w;
        const ns = info[node] === 0 ? s + 1 : s;
        
        // 엣지케이스: 늑대의 수가 양의 수보다 같거나 많다면 return
        if (nw >= ns) return;
        
        answer = Math.max(answer, ns);
        
        // 2) 현재 노드에서 다음 노드로 들어가기 위한 후보 노드 추가
        const nextNodes = [...candidates, ...graph[node]];
        
        // 3) 그 다음 후보 노드로 dfs 돌리기
        for (let i = 0; i < nextNodes.length; i++) {
            const next = nextNodes[i]
            dfs(next, nw, ns, nextNodes.filter((_, idx) => idx !== i));
        }
        
    };
    
    dfs(0, 0, 0, []);
    
    return answer;
}