[프로그래머스#JS] 가장 먼 노드

문제

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

1. BFS 이용해 depth를 구해 가장 큰 값의 개수 구하기
2. 다익스트라 알고리즘을 이용해 1번 노드에서 가장 먼 노드들의 개수 세기

코드

BFS

/// 1. BFS 이용
function solution(n, vertex) {
  let arr = [];
  let check = new Array(n + 1).fill(false);
  let depth = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    arr[i + 1] = [];
  }

  for (let i = 0; i < vertex.length; i++) {
    arr[vertex[i][0]].push(vertex[i][1]);
    arr[vertex[i][1]].push(vertex[i][0]);
  }

  let q = [];
  check[1] = true;
  for (let i = 0; i < arr[1].length; i++) {
    q.push(arr[1][i]);
    check[arr[1][i]] = true;
    depth[arr[1][i]] = 1;
  }

  let cnt = 1;
  while (true) {
    if (q.length === 0) break;
    let temp = q[0];
    q.shift();

    for (let i = 0; i < arr[temp].length; i++) {
      let nextNode = arr[temp][i];
      if (check[nextNode]) continue;
      check[nextNode] = true;
      depth[nextNode] = depth[temp] + 1;
      q.push(nextNode);
    }
  }

  let max = Math.max.apply(null, depth);
  let ans = 0;
  for(let i = 0 ; i < depth.length; i++){
    if(depth[i] === max) ans++;
  }

  return ans;
}

다익스트라

// 다익스트라 이용
function solution(n, edge) {
  
  // 우선순위큐 구현
  class PriorityQueue {
    constructor(dist) {
      this.queue = [];
      this.dist = dist;
    }

    enqueue(nodeIndex) {
      this.queue.push(nodeIndex);
    }

    dequeue() {
      let entry = 0;
      let entryIndex = this.queue[entry];

      this.queue.forEach((nodeIndex, idx) => {
        if (this.dist[entryIndex] > this.dist[nodeIndex]) {
          entryIndex = nodeIndex;
          entry = idx;
        }
      });

      return this.queue.splice(entry, 1);
    }
  }

  const map = new Array(n).fill(null).map(() => new Array());
  for (let path of edge) {
    const [u, v] = path;

    map[u - 1].push([v - 1, 1]);
    map[v - 1].push([u - 1, 1]);
  }

  const dist = new Array(n).fill(Infinity);
  const isVisited = new Array(n).fill(false);
  const pq = new PriorityQueue(dist);

  pq.enqueue(0);
  dist[0] = 0;

  // 다익스트라
  while (pq.queue.length > 0) {
    const [curr] = pq.dequeue();
    console.log(curr);

    if (isVisited[curr]) continue;

    isVisited[curr] = true;

    for (const [next, w] of map[curr]) {
      if (dist[next] > dist[curr] + 1) {
        dist[next] = dist[curr] + 1;
        pq.enqueue(next);
      }
    }
  }

  return dist.filter((v) => v ===  Math.max(...dist)).length;
}

인접 행렬로 다익스트라를 구현하면 시간 복잡도가 최대 N^2이라 우선순위큐로 다익스트라를 구현하는게 힘들었습니다.