양과 늑대

Link

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

Deadline

Jan 29, 2022

Status

Archived

Type

BFS

DFS

dynamic programming

풀이

은찬


function solution(info, edges) {
    let answer = 1;
    const length = info.length;
    const graph = Array.from({length}, () => []);
    
    const dfs = (current, nextNodes) => {
        let [currentNode, sheep, wolves] = current;
        const newNextNodes = [...nextNodes];
        const index = newNextNodes.indexOf(currentNode);
        
        sheep += !info[currentNode];
        wolves += info[currentNode];
        answer = Math.max(answer, sheep);
        
        if(sheep === wolves){
            return;
        }
        
        if(graph[currentNode].length){
            newNextNodes.push(...graph[currentNode]);
        }
        
        newNextNodes.splice(index, 1);
        
        for(const nextNode of newNextNodes){   
            dfs([nextNode, sheep, wolves], newNextNodes);
        }
    }
    
    for(let i = 0; i < edges.length; i++){
        const [from, to] = edges[i];
        
        graph[from].push(to);
    }
    
    dfs([0, 0, 0], [0]);
    
    return answer;
}

재영


class Queue {
  constructor(info) {
    this.info = info;

    this.arr = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(val) {
    this.arr[this.rear] = val;
    this.rear += 1;
  }

  dequeue() {
    const value = this.arr[this.front];
    delete this.arr[this.front];
    this.front += 1;
    return value;
  }

  size() {
    return this.rear - this.front;
  }

  sort() {
    this.arr.sort((a, b) => this.info[a[0]] - this.info[b[0]]); // sheep -> priority
    return this.arr;
  }
}

const solution = (info, edges) => {
  const graph = {};

  for (let [from, to] of edges) {
    if (!graph[from]) graph[from] = [];
    graph[from].push(to);
  }

  const queue = new Queue(info);
  const visited = Array(info.length).fill(false);
  let maxSheep = 0;

  queue.enqueue([0, 0, 0, [...(graph[0] || [])], [...visited]]); // now, nowSheep, nowWolves, possibleVisit

  while (queue.size()) {
    const [now, nowSheep, nowWolves, possibleVisit, nowVisited] =
      queue.dequeue();
    nowVisited[now] = true;

    const nextSheep = nowSheep + !info[now];
    const nextWolves = nowWolves + info[now];
    if (nextSheep <= nextWolves) continue;

    maxSheep = Math.max(maxSheep, nextSheep);

    possibleVisit.push(...(graph[now] || []));
    for (let next of possibleVisit) {
      if (nowVisited[next]) continue;

      queue.enqueue([
        next,
        nextSheep,
        nextWolves,
        possibleVisit.filter((v) => v !== next),
        [...nowVisited],
      ]);
    }
  }

  return maxSheep;
};