가장 먼 노드

문제 설명

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

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

제한사항

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

입력

n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

출력

3

입출력 예 설명

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

데브코스에서 그래프 강의를 듣고 실습문제를 풀어보려고 한다.
평소에 알고리즘 문제에 약해서 DFS, BFS는 시도조차 못하고 있었다. 이 문제도 마찬가지였다.
입력값 vertex가 "이미 그래프가 만들어져 있는거 아닌가..?" 싶어서

const edgeMap = new Map();
vertex.forEach(([node, edge], index) => edgeMap.set(node, {
  node:edge
}))
...

이런식으로 풀어보려다가 아무리 생각해도 이건 아닌것 같아 문제풀이 강의를 들으면서 천천히 이해했다.

풀이

먼저 그래프를 만들어줘야한다.
이 문제에서 핵심 키워드는 간선은 양방향이다.

const graph = Array.from(Array(n + 1), () => [])

for(const [from,to] of edge) {
  graph[from].push(to);
  graph[to].push(from);
}

1번 노드에서 가장 멀리 있는 노드의 거리를 구해야한다.
각 정점의 거리를 기록할 수 있도록

const distance = Array(n+1).fill(0);
distance[1] = 1;	// 1번노드를 거리 1로

그리고 이제 BFS (너비 우선 탐색)를 구현해야한다.
(BFS, DFS는 다른 포스트에 따로 개념 정리를 해야겠다)

BFS는 큐나 연결리스트로 구현 가능하다.

const queue = [1];	// 1번 노드를 기준으로
while(queue.length > 0) {
  const from = queue.shift();
  
  for(const node of graph[from]) {
    if(distance[node] === 0) {	// 한번도 가지 않은 노드라면
      queue.push(node);
      distance[node] = distance[from] + 1;
    }
  }
}
console.log(distance);
//	
// [
//  0, 1, 2, 2,
//  3, 3, 3
// ]

마지막으로 가장 멀리(3) 있는 노드들 갯수를 카운트해서 출력하면 된다.

const max = Math.max(...distance);
return distance.filter(item === max).length;

전체코드

function solution(n, edge) {
    const graph = Array.from(Array(n + 1), () => [])
    
    for(const [from, to] of edge) {
        graph[from].push(to);
        graph[to].push(from);
    }
    
    const distance = Array(n+1).fill(0);
    distance[1] = 1;
    
    // BFS
    const queue = [1];
    while(queue.length > 0) {
        const from = queue.shift();
        
        for(const node of graph[src]) {
            if(distance[node] === 0) {
                queue.push(node);
                distance[node] = distance[from] + 1
            }
        }
    }
  
    const max = Math.max(...distance);
    return distance.filter(item => item === max).length;
}

어렵지만 다른 문제도 풀어봐야겠다😇