[js문제풀이] 가장 먼 노드

문제

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

접근 및 풀이

bfs를 이용해 풀었다. 가장 먼 노드를 찾기 위해 노드를 순회할 때 마다 큐에 현재 깊이와 도달 가능한 인덱스를 저장했다. 순회하는 노드의 깊이가 최대 노드보다 클 때 count를 1로 초기화 하면서 먼 노드의 개수를 갱신했다. 정확도는 통과했지만 효율성이 많이 떨어지는 것 같았다. 다른 사람의 풀이와 비교해보니 방문한 노드를 걸러낼 때 visited를 배열로 구현하고 includes 메서드로 확인 했는데 그 부분이 비효율적이었던 것 같다. visited를 객체 형태로 프로퍼티 키값을 인덱스로 사용하면 O(1)로 바로 접근할 수 있기 때문에 훨씬 빨라진다. 

다른 사람 풀이

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

코드

function solution(n, edge) {
  const graph = Array.from(new Array(n + 1), () => []);
  edge.forEach((e) => {
    if (graph[e[0]]) graph[e[0]].push(e[1]);
    else graph[e[0]] = [e[1]];
    if (graph[e[1]]) graph[e[1]].push(e[0]);
    else graph[e[1]] = [e[0]];
  });
  const queue = [[1, 0]];
  const visited = [1];
  let count = 0;
  let maxDepth = 0;
  while (queue.length !== 0) {
    const current = queue.shift();
    if (maxDepth === current[1]) {
      count++;
    } else if (maxDepth < current[1]) {
      maxDepth = current[1];
      count = 1;
    }
    graph[current[0]].forEach((des) => {
      if (visited.includes(des)) return;
      queue.push([des, current[1] + 1]);
      visited.push(des);
    });
  }
  return count;
}

출처

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