1.가장 먼 노드

일단 지금은 캠프교육중이라 시간이 없어서 이렇게 정리해놓는다. 시간 나면 나중에 그림으로 그려가면서 해봐라 이해 바로 된다.

1번 노드로 부터 가장 멀리 떨어져 있는 노드의 갯수를 구하면 된다.

구럼, n,vertex가 요런식으로 주어진다고 했을때 최종 리턴값은 3이다.( 4, 5, 6번 노드 )

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

자 그럼 vertex를 그림으로 나타내 보겠다.

코드!

pseudo code

while안에서 que를 shift하면서 bfs방식으로 문제를 풀거다.

1. 방문 여부와 1번 노드와의 거리를 측정하는 visited를 만듬.

2. que에 일단 1번 노드를 push함.

3. adjList 안에서 각 노드와 인접한 노드의 리스트를 만듬.

4. que에서 shift한 있는 노드와 인접한 노드의 리스트를 선택한다.

   4-1. 인접한 노드 리스트를 순회하면서 방문하지 않았던 노드를 visted로 알아낸다.

   4-2. 방문하지 않았으면 방문하지 않았던 노드 위치값을 shift한 노드(부모노드)의 위치 + 1값으로 치환한다.(부모 노드와의 거리는 당연히 +1 이기 때문에)

5. 가장 거리가 먼 노드의 값을 max에 담고 max와 같은 노드의 갯수를 visited안에서 filter한다음 length를 리턴한다.

const farmost = (n, edge) => {
  const visited = new Array(n + 1).fill(-1); // 방문했는지 체크하는 배열 -1 : 방문x, 0: 방문o
  const queue = [1]; // bfs를 하기위한 노드
  const adjList = new Array(n + 1).fill(null).map(() => Array()); // 간선 배열

  // 0번 노드는 없으니깐 방문한걸로 치고
  // 1번 노드는 , 1번 노드에서 부터 시작하므로 방문한걸로 친다.
  visited[0] = 0;
  visited[1] = 0;

  // 인접 리스트를 만든다.
  for (let i of edge) {
    adjList[i[0]].push(i[1]);
    adjList[i[1]].push(i[0]);
  }

  //모든 노드를 방문할때까지 계속한다.
  while (queue.length > 0) {
    //방문한 노드를 큐에서 뺀다.
    const node = queue.shift();
    //edge를 순회하며 다음 방문할 노드를 찾는다.
    //방문할 노드가 있다면
    if (adjList[node]) {
      adjList[node].forEach((n) => {
        //이미 방문했던 노드라면 엣지를 그냥 skip한다.
        if (visited[n] === -1) {
          // 방문하지 않았던 노드라면 노드를 방문해준다.
          queue.push(n);
          // node의 이웃 node들을 순회한다. 그리고 이웃 node가(visited[n]) 부모 노드((visited[node])와 얼마나 떨어져 있는지 visited에 입력한다
          // 부모노드와 1사이에 거리는 이미 visited에 저장되어있다.
          // 그래서 이웃노드는 부모노드에서 1만 더하면 1번 노드와의 거리가 되는것이다. 자동적으로.
          visited[n] = visited[node] + 1;
        }
      });
    }
  }
  // visited = [0, 0, 1, 1, 2, 2, 2]
  // 그래서 가장 먼 거리의 노드 길이를 구한다음에 그 노드길이와 같은 노드가 무엇인지 찾기만 하면 끝!
  const maxNum = Math.max(...visited);
  return visited.filter((e) => e === maxNum).length;
};

아주 깔끔하고 쉽다.