🕊 Link

Lv3. 가장 먼 노드 Javascript
https://programmers.co.kr/learn/courses/30/lessons/49189

TEST CASE

const n = 6
const vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
console.log(solution(n, vertex));

자바스크립트로 구현하는 너비우선탐색(BFS) 깊이우선탐색(DFS)
*객체 그래프

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const bfs = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

[JS] 프로그래머스 - 가장 먼 노드
*배열 그래프(length = n)

const solution = (n, edge) => {
  const graph = getGraph(n, edge);
  const visited = new Array(n).fill(false);
  const dist = new Array(n).fill(0);
  const q = [];

  q.push({v:0, curDist:0});
  visited[0] = true;

  BFS(dist, q, visited, graph);

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

const BFS = (dist, q, visited, graph) => {
  while(q.length){
    const {v, curDist} = q.shift();
    const adj = graph[v];

    for(let i=0; i<adj.length; i++){
      const v = adj[i]-1;
      if(!visited[v]){
        visited[v] = true;
        q.push({v, curDist: curDist+1});
      }
    }
    dist[v] = curDist;
  }
}

const getGraph = (n, edge) => {
  const graph = Array.from({length:n}, (_) => []);
  while(edge.length){
    const [from, to] = edge.shift();
    graph[from-1].push(to);
    graph[to-1].push(from);
  }
  return graph;
}

프로그래머스: 김동욱 , 테스트 , 김민재
*객체 그래프

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;
}

(javascript) 프로그래머스 가장 먼 노드
*그래프X

function solution(n, edge) {
  var answer = 0;
  return bfs(edge, 1, n);
}

function bfs(arr, start, end) {
  var visited = new Array(end + 1)
  var level = new Array(end + 1)
  var queue = [start]
  level[0] = 0
  level[start] = 0
  visited[start] = true
  var lev
  while (queue.length) {

    var node = queue.shift()
    lev = level[node] + 1
    for (var edge of arr) {
      if (edge[0] == node && visited[edge[1]] == undefined) {
        queue.push(edge[1])
        visited[edge[1]] = true
        level[edge[1]] = lev
      }
      else if (edge[1] == node && visited[edge[0]] == undefined) {
        queue.push(edge[0])
        visited[edge[0]] = true
        level[edge[0]] = lev
      }
    }
  }
  return level.filter((i) => i == lev - 1).length
}

상기 코드 수정본

function solution(n, edges) {
  return bfs(edges, 1, n);
}

function bfs(edges, start, end) {
  const visited = new Array(end + 1).fill(false)
  const cost = new Array(end + 1).fill(0)
  const q = [start]

  cost[0] = 0
  cost[start] = 0
  visited[start] = true

  let curCost = 0
  while (q.length) {
    console.log(q);
    const node = q.shift()
    curCost = cost[node] + 1
    for (const edge of edges) {
      const [from, to] = edge
      if (from == node && visited[to] == false) {
        q.push(to)
        visited[to] = true
        cost[to] = curCost
      }
      else if (to == node && visited[from] == false) {
        q.push(from)
        visited[from] = true
        cost[from] = curCost
      }
    }
  }
  return cost.filter((v) => v == curCost - 1).length
}