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

문제 출처

프로그래머스 lev3 - 가장 먼 노드

나의 풀이

1을 기준으로 가장 먼 레벨을 찾으면 되는 문제.

bfs 풀이

function solution(n, edge) {
  const list = new Array(n).fill().map(_ => [])

  for(const [a, b] of edge){
    list[a-1].push(b-1)
    list[b-1].push(a-1)
  }

  const dist = [1] // 최단거리 
  const queue = [0] // 노드

  while(queue.length){
    const curr = queue.shift()

    for(const next of list[curr]){
      if(!dist[next]){
        dist[next] = dist[curr] + 1
        queue.push(next)
      }
    }
  }

  const max = Math.max(...dist)
  return dist.filter(_ => _ === max).length
}

console.log(solution(
  6, 
  [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))

다른 풀이

reduce 메서드를 사용한 list 생성

function solution(n, edges) {
  // make adjacent list
  const adjList = edges.reduce((G, [from, to]) => {
      G[from] = (G[from] || []).concat(to);
      G[to] = (G[to] || []).concat(from);
      return G;
  }, {});

  // do BFS
  const queue = [1];
  const visited = {1: true};
  const dist = {1: 0};
  while(queue.length > 0) {
      const node = queue.shift();

      if (adjList[node]) {
          adjList[node].forEach(n => {
              if (!visited[n]) {
                  queue.push(n);
                  visited[n] = true;
                  const d = dist[node] + 1;
                  if (dist[n] == undefined || d < dist[n]) {
                      dist[n] = d;
                  }
              }
          });
      }
  }

  const dists = Object.values(dist);
  const maxDist = Math.max(...dists);
  return dists.filter(d => d == maxDist).length;
}