가장 먼 노드

문제설명

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

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

제한사항

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

입출력 예

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

입출력 예 설명

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

문제풀이

선택한 간선을 줄여가면서, 다음에 선택된 간선이 없으면 그 전의 노드들이 1번에서 가장 먼 노드이다.

1. check배열을 만들고, 1을 넣어줌(처음 시작은 항상 1)
2. edge배열을 줄여주는데, edge배열 원소 중 check 배열의 안에 있는 노드들에 연결되어 있는 간선들을 제거한다.
3. 제거되는 간선들은 newCheck 즉 그 다음 check배열이 되어야하니 newCheck 배열을 선언하고 따로 저장해준다.
4. check배열 안의 노드에 연결된 간선들을 제거한 edge배열이 길이가 0이고, newCheck배열이 길이가 0.
   즉, 현재 노드가 1번에서 가장 먼 노드일 때, answer은 check의 length가 되고 break해서 while문을 끝내준다.
5. 만약 edge, newCheck의 길이가 0이 아니라면, check = newCheck으로 만들어 주면 되는데, 중복이 있는 경우가 있으니 제거해준다.

function solution(n, edge) {
  var answer = 0;
  let check = [1];
  while (true) {
    let newCheck = [];
    edge = edge.filter(e => {
      if (check.includes(e[0]) && check.includes(e[1])) return false;
      if (check.includes(e[0])) {
        newCheck.push(e[1]);
        return false;
      }
      if (check.includes(e[1])) {
        newCheck.push(e[0]);
        return false;
      }
      return true;
    });
    if (edge.length === 0 && newCheck.length === 0) {
      answer = check.length;
      break;
    }
    check = [...new Set(newCheck)];
  }

  return answer;
}

아쉬운 점 || 느낀 점

레벨3은 항상 처음 풀이 방식이 틀리고 나서 다른 방식을 생각하고 맞는 것 같다.
풀이 자체는 어렵지 않은데 처음 풀이 방식으로 도전한 뒤에 시간초과나 빼먹은 조건들을 고려할 때,
처음 풀이 방식이 좋은 방법이 아니거나 아닌 것을 알았을 때 다른 방법을 시도해서 시간이 오래걸린다.
좀 더 문제 풀이 방식이 효율적인 방법을 찾는 것도 중요한 것 같다.