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

[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

from http://fffo.tistory.com/170 by ccl(A) rewrite - 2021-10-16 20:00:40