[JS] 양과 늑대 - dfs인데 왔다리갔다리 함..

dfs 응용입니다. 양만 먹어야 된대요.같이 한 번 볼까요?

---

문제 요약

 

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

---

입출력 예

info	edges	result
[0,0,1,1,1,0,1,0,1,0,1,1]	[[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]]	5
[0,1,0,1,1,0,1,0,0,1,0]	[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]]	5

 

접근 방법

양을 먹었을 때 visited를 전부 false로 바꿔줍시다!

그러면 한 루트로 깊게 들어갔다가 다시 나와서 다른 경로로 들어갈 수 있습니다.

다만, 이랬을 때 사이클이 발생할 위험이 생기기 때문에..

한번 간 경로는 표시를 해줄 필요가 있겠네요.

 

visited를 위한 visited를 만든다뇨...

 

정답 코드

function solution(info, edges) {
    const nodeMap = new Map();
    let currNode = 0;
    const visited = Array.from({ length: info.length }, () => false);
    const result = [];
    
    for (let node = 0; node < info.length; node++) {
        const next = edges.filter(v => v.includes(node)).flat(1).filter(v => v !== node);
        nodeMap.set(node, next);
    }
    dfs(0, { sheep: 0, wolf: 0 }, visited, []);
    
    return Math.max(...result);
    
    
    function dfs(node, currState, visited, onceVisited) {
        let { sheep: sheep, wolf: wolf } = currState;
        const currVisited = [...visited];
        const currOnceVisited = [...onceVisited];
        
        if (currVisited[node]) { result.push(sheep); return; }
        if (info[node] === 0 && !currVisited[node]) {
            if (!currOnceVisited.includes(node)) {
                sheep++;
                visited.forEach((_, i) => currVisited[i] = false);
                currOnceVisited.push(node);
            }
        } else if (info[node] === 1) {
            if (!currOnceVisited.includes(node)) {
                wolf++;
                currOnceVisited.push(node);
            }
        }
        if (wolf >= sheep) { result.push(sheep); return; }
        currVisited[node] = true;
        
        const nexts = nodeMap.get(node);
        for (const next of nexts) {
            dfs(next, { sheep: sheep, wolf: wolf }, currVisited, currOnceVisited);
        }
    }
}

 

팁 1. 경로 HashMap으로 찾는 시간을 줄이자!

for (let node = 0; node < info.length; node++) {
        const next = edges.filter(v => v.includes(node)).flat(1).filter(v => v !== node);
        nodeMap.set(node, next);
    }

 

간선 문제에선 언제나 꼭 명심합시다!

루프나 재귀 함수 밖에서 hashMap을 만들어주면 꽤나 쏠쏠해요.

 

팁 2. onceVisited와 visited의 관계

if (currVisited[node]) { result.push(sheep); return; }
        if (info[node] === 0 && !currVisited[node]) {
            if (!currOnceVisited.includes(node)) {
                sheep++;
                visited.forEach((_, i) => currVisited[i] = false);
                currOnceVisited.push(node);
            }
        } else if (info[node] === 1) {
            if (!currOnceVisited.includes(node)) {
                wolf++;
                currOnceVisited.push(node);
            }
        }

 

이 로직이 이 문제의 핵심입니다.

 

1. 이미 방문한 적 있는 노드라면 return;
2. 양인 경우,
    1) 진짜 첫 방문인 경우
    2) 방문했는데 false로 바꿔줘서 사실 첫 방문이 아닌 경우
3. 늑대인 경우,

 

각 구조에서 양은 2-1) 경우만 가산을 해주면 되고, 늑대는 가산해줄 때, onceVisited까지 같이 넣어줍시다!

---

진짜 dfs 오랜만에 풀어서 그런지 약간 버벅였네요.

그럼 이만!