Portfolio

💡

카카오 인턴 문제네요. ~~이걸 풀면 나도 카카오...?!~~

풀이

은찬


class Queue{
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }

    push(value) {
        this.queue[this.rear++] = value;
    }

    pop() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front++;

        return value;
    }

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

const solution = (n, path, order) => {
    const graph = Array.from({length: n}, () => []);
    const visited = Array(n).fill(false);
    const orderPath = Array(n);
    const waitPath = Array(n).fill(-1);
    const queue = new Queue();
    let visitedCount = 1;
    
    for(let i = 0; i < path.length; i++){
        const [from, to] = path[i];
        
        graph[from].push(to);
        graph[to].push(from);
    }
    
    for(let i = 0; i < order.length; i++){
        const [A, B] = order[i];
        
        orderPath[B] = A;
    }
    
    if(orderPath[0]){
        return false;
    }
    
    queue.push(0);
    visited[0] = true;
    
    while(queue.size()){
        const currentPath = queue.pop();
        
        for(const nextPath of graph[currentPath]){
            const prevPath = orderPath[nextPath];
            
            if(prevPath && !visited[prevPath]){
                waitPath[prevPath] = nextPath;
                continue;
            }
            
            if(visited[nextPath]){
                continue;
            }
            
            if(waitPath[nextPath] !== -1){
                visited[waitPath[nextPath]] = true;
                queue.push(waitPath[nextPath]);
                visitedCount++;
            }
            
            visited[nextPath] = true;
            queue.push(nextPath);
            visitedCount++;
        }
    }
    
    return visitedCount === n;
}

재영

시간 초과(정확성 O)


class Queue {
  constructor() {
    this.arr = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.arr[this.rear] = value;
    this.rear += 1;
  }

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

    return value;
  }

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

const dfs = (node, undirectedGraph, visited, directedGraph) => {
  visited[node] = true;
  for (let now of undirectedGraph[node]) {
    if (visited[now]) continue;

    directedGraph[node] = directedGraph[node]
      ? directedGraph[node].concat([now])
      : [now];

    dfs(now, undirectedGraph, [...visited], directedGraph);
  }
  return directedGraph;
};

const topologySort = (graph, indegree) => {
  const queue = new Queue();
  let cnt = 0;
  queue.enqueue(0);

  while (queue.getLength()) {
    const now = queue.dequeue();
    cnt += 1;
    if (!graph[now]) continue;
    for (let next of graph[now]) {
      if (!indegree) continue;

      indegree[next] -= 1;
      if (!indegree[next]) {
        queue.enqueue(next);
      }
    }
  }

  return cnt;
};

const solution = (n, path, order) => {
  var answer = true;

  const indegree = Array(n).fill(0);
  const visited = Array(n).fill(false);

  const undirectedGraph = {};

  // create undirected graph
  for (let [from, to] of path) {
    undirectedGraph[from] = undirectedGraph[from]
      ? undirectedGraph[from].concat([to])
      : [to];
    undirectedGraph[to] = undirectedGraph[to]
      ? undirectedGraph[to].concat([from])
      : [from];
  }

  // create directed graph to proceed to topology sort
  const directedGraph = dfs(0, undirectedGraph, visited, {});

  // update directed graph for assign indegree value
  for (let [from, to] of order) {
    directedGraph[from] = directedGraph[from]
      ? directedGraph[from].concat([to])
      : [to];
  }

  // assign indegree array with fan-in value
  for (let node in directedGraph) {
    for (let leaf of directedGraph[node]) {
      indegree[leaf] += 1;
    }
  }

  const cnt = topologySort(directedGraph, indegree);

  return n === cnt;
};

최적화 진행, 통과


class Queue {
  constructor() {
    this.arr = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.arr[this.rear] = value;
    this.rear += 1;
  }

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

    return value;
  }

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

const dfs = (node, undirectedGraph, visited, directedGraph, indegree) => {
  visited[node] = true;
  for (let now of undirectedGraph[node]) {
    if (visited[now]) continue;
    
    if (!directedGraph[node]) directedGraph[node] = [];
    directedGraph[node].push(now)
    
    indegree[now] += 1
    dfs(now, undirectedGraph, visited, directedGraph, indegree);
  }
  return {indegree, directedGraph};
};

const topologySort = (graph, indegree) => {
  const queue = new Queue();
  let cnt = 0;
  queue.enqueue(0);

  while (queue.getLength()) {
    const now = queue.dequeue();
    cnt += 1;
      
    if (!graph[now]) continue;
    for (let next of graph[now]) {
      indegree[next] -= 1;
      if (!indegree[next]) {
        queue.enqueue(next);
      }
    }
  }

  return cnt;
};

const solution = (n, path, order) => {
  var answer = true;

  const visited = Array(n).fill(false);

  const undirectedGraph = {};

  // create undirected graph
  for (let [from, to] of path) {
    if (!undirectedGraph[from]) undirectedGraph[from] = [];
    if (!undirectedGraph[to]) undirectedGraph[to] = [];
    undirectedGraph[from].push(to)
    undirectedGraph[to].push(from)
  }

  // create directed graph to proceed to topology sort
  const {indegree, directedGraph} = dfs(0, undirectedGraph, visited, {}, Array(n).fill(0));

  // update directed graph for assign indegree value
  for (let [from, to] of order) {
  if (!directedGraph[from]) directedGraph[from] = [];
    directedGraph[from].push(to)
    indegree[to] += 1;
  }

  const cnt = topologySort(directedGraph, indegree);

  return n === cnt;
};

동굴탐험

풀이

시간 초과(정확성 O)

최적화 진행, 통과