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

📖 문제

level3 가장 먼 노드

✏️ 나의 풀이

보통 최단 거리만을 풀어왔기에 어떻게 해야 가장 먼 노드를 풀어야할지 고민했다.

그래서 각각 노드가 1번 노드와 얼마나 떨어져있는지를 저장하는 배열을 새로 만들어 두었다.

const dis = new Array(n + 1).fill(0);

새로운 노드를 queue에 저장하면서 동시에 1번 노드와의 거리를 저장하였다.

또한, queue에는 노드와 해당 노드가 1번 노드와 얼마나 떨어져있는지를 배열의 형태로 저장해두었다.

dis[v] = dis[v] === 0 ? d + 1 : dis[v];
queue.push([v, dis[v]]);

1번 노드와 가장 먼 거리를 저장하는 max 라는 변수를 선언한 후 queue에서 새로운 값을 꺼낼때 max를 업데이트 시켜주었다.

const [value, d] = queue.shift();
max = Math.max(d, max);

최종적으로 모든 노드를 방문하고 떨어져있는 거리를 저장하는 배열에 max와 같은 값이 몇개인지를 찾아 이를 반환해주었다.

return dis.filter((v) => v === max).length;

👩‍💻 코드

function solution(n, edge) {
  var answer = 0;
  const graph = new Array(n + 1).fill(0).map((_) => []);
  for (let v of edge) {
    const [a, b] = v;
    graph[a].push(b);
    graph[b].push(a);
  }
  const bfs = (start) => {
    const queue = [...graph[start].map((v) => [v, 1])];
    const visited = new Array(n + 1).fill(false);
    const dis = new Array(n + 1).fill(0);
    for (let v of queue) {
      const [n, d] = v;
      dis[n] = d;
    }
    visited[start] = true;
    let max = 0;
    while (queue.length) {
      const [value, d] = queue.shift();
      max = Math.max(d, max);
      for (let v of graph[value]) {
        if (visited[v]) continue;
        visited[v] = true;
        dis[v] = dis[v] === 0 ? d + 1 : dis[v];
        queue.push([v, dis[v]]);
      }
    }
    return dis.filter((v) => v === max).length;
  };
  return bfs(1);
}