[JavaScript] 프로그래머스 코딩테스트 레벨 3 : 가장 먼 노드

📌  문제

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

---

📌  풀이

알아야 하는 것

• 주어진 정보로 그래프를 구현하는 기본 템플릿

 

graph를 선언할 때 배열의 길이가 n+1인 배열을 만들되 그 안을 다 빈 배열 [] 로 채워준다.

왜 n+1 이냐면 배열은 0부터 시작하지만, 그래프가 주어질 때 노드 번호는 1부터 시작한다. 따라서 처음부터 배열을 만들 때 주어진 노드의 수보다 하나 더 크게 공간을 만든다. 그래야 0부터 시작해서 노드 번호의 끝까지 담을 수 있기 때문이다. 콘솔에 찍어 확인해 보면 배열의 0번째 인덱스에는 해당하는 노드가 없어서 삽입되지 않고 비어 있음을 알 수 있다.

 

// 배열은 0부터 시작하지만 그래프가 주어질 때는 노드 번호는 1부터 시작한다.
const graph = Array.from(Array(n + 1), () => []);

// 구조 분해 할당을 이용해 서로의 좌표에 연결된 노드들을 삽입한다.
for (let [from, to] of edge) {
  graph[from].push(to);
  graph[to].push(from);
}

 

이건 방금 알게 된 건데 Array.from(Array(n+1), () => [])랑 Array(n+1).fill([]) 이랑 같은 것 같은데 결과가 달랐다. 이유를 알아 보니 Array.from 메소드는 주어진 이터러블 객체나 유사 배열 객체를 배열로 변환하는 메서드로, 각 요소마다 새로운 배열 객체가 생성되어 참조된다. 즉 각 요소는 독립적인 배열 객체를 갖게 된다. 반면 fill의 경우 주어진 값을 배열의 모든 인덱스에 복사하는데, 할당된 값이 객체의 경우 모두 동일한 객체를 참조하게 되는 것으로 그래프의 구조를 구현할 수가 없었던 것이다.

 

// Array.from
const array = Array.from(Array(3), () => []);
array[0].push(1);

console.log(array); // 출력: [[1], [], []]

// fill
const array = Array(3).fill([]);
array[0].push(1);

console.log(array); // 출력: [[1], [1], [1]]

 

그러니 그래프를 구현할 때는 간단하게 저 템플릿을 체화하도록 하자!

 

구할 것

• 그래프 구현
  • 그래프를 구현하면 아래와 같은 모양이 된다. 배열의 0번째 배열은 잘 비어져 있다. 인덱스를 기준으로 노드 1은 3, 2와 연결되어 있다는 뜻이다. 입출력 예 그림과 동일한 모양이 갖춰졌다.

• 방문 여부 확인
  • 각 노드별로 방문했는지 여부를 체크해야 한다. const visited = Array(n+1).fill(false) 라는 배열을 생성한다. 하면 길이가 n+1인 배열에 모두 false가 들어간다. 이 문제는 DFS로도 구현할 수 있을 것 같지만 문제에서 '최단 경로'로 이동했을 때 라고 명시하고 있고, JS로 그래프를 탐색할 때는 BFS가 DFS보다 시간초과의 영향을 덜 받는다고 한다. (좀 더 알아볼 것) 따라서 BFS로 그래프를 구현하기 위해 큐를 쓸 것이다. 
  • 시작 노드인 1번 노드를 queue에 먼저 넣고, visited에서도 1번을 방문 처리(true) 해준다.  
  • queue의 길이가 있는 한 계속 while문이 진행되고, 큐이기 때문에 현재 노드를 앞부터 shift로 제거한다. 큐에서 제거하고 난 후, graph[1]의 값을 for문과 next라는 변수로 순회한다. 이 때 graph[1]의 값 3이 visited에 false라면 (=방문하지 않았다면) visited[3]의 값을 현재 경로에서 +1을 해준다. 간단하게 방문하지 않은 노드라면 이 노드가 1에서 얼마나 떨어졌는지 알아봐야 하는데, 이 알아보는 기준이 노드 1에 1을 더한 값인 것이다. (graph[1] 기준) 
  • graph[1]의 값이 [3, 2]인데 둘 다 방문하지 않았으니 visited 배열에 visited[1](true)+1로 2가 되는 것이다.
  • 이러면 다음 큐에는 [3, 2]가 들어와 있고, 노드 3번부터 다시 똑같은 과정을 반복한다. 3의 경우 [6, 4, 2, 1]인데 6의 경우 방문하지 않았으니 visited[3]+1을 해야 한다. visited[3]은 위에서 2가 되었으니 1을 추가하면 3이 된다. 실제로 그래프에서도 6의 경우 루트 노드 1을 기준으로 3레벨에 있다.
• 가장 멀리 떨어진 노드 구하기
  • while문을 다 돌고 나면 visited = [false, true, 2, 2, 3, 3, 3]이 된다. 0번째의 false는 위에서 설명했고 1번째 true는 방문 처리를 true로 하고 가서 그렇다. 이 때 우리가 구해야 하는 것은 가장 큰 수가 몇 개 있냐는 것이다.
  • 가장 큰 수를 const max = Math.max(...visited)라고 하면 3이 나온다. 3의 개수를 구하기 위해 visited에 filter를 써서 max값만 있는 경우의 length를 구한다.

function solution(n, edge) {
  const graph = Array.from(Array(n + 1), () => []);

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

  const visited = Array(n + 1).fill(false);
  const queue = [1];
  visited[1] = 1; // 시작 노드를 방문한 것으로 표시

  while (queue.length) {
    const current = queue.shift();
    for (const next of graph[current]) {
      if (!visited[next]) {
        // 방문하지 않은 노드인 경우에만 처리
        visited[next] = visited[current] + 1;
        queue.push(next);
      }
    }
  }
  const max = Math.max(...visited);
  return visited.filter((v) => v === max).length;
}

재귀를 약간 이해하고 왔더니 이제 BFS DFS가 기다리고 있다.

오늘은 팀원 분이 푸신 문제를 따라 푼 것이지만 앞으로는... 어떡하지... 🥹