[JS] 프로그래머스 코딩테스트 연습 | 그래프 - 가장 먼 노드

문제 링크 : 그래프 > 가장 먼 노드

1. 문제

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

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

2. 입출력 예

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

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

---

3. 풀이

1. shift를 사용하는 경우

function solution(n, edge) {
  // 인접 리스트
  const graph = Array.from(Array(n + 1), () => []);
  console.log(graph);

  // 양방향 그래프 완성
  for (const [start, end] of edge) {
    graph[start].push(end);
    graph[end].push(start);
  }

  // 정점의 거리 기록
  const dist = Array(n + 1).fill(0);
  dist[1] = 1;

  // BFS
  const queue = [1];
  while (queue.length > 0) {
    const src = queue.shift(); // shift는 O(n)이지만 요소가 적을 경우에는 자바스크립트 엔진에서 최적화 해줌
    for (const dest of graph[src]) {
      if (dist[dest] === 0) {
        queue.push(dest);
        dist[dest] = dist[src] + 1;
      }
    }
  }
  console.log(dist);
  const max = Math.max(...dist);

  return dist.filter((item) => item === max).length;
}

---

2. queue를 사용하는 경우

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;
    return value;
  }
  isEmpty() {
    return this.front === this.rear;
  }
}

function solution(n, edge) {
  // 인접 리스트
  const graph = Array.from(Array(n + 1), () => []);
  // 그래프 완성
  for (const [start, end] of edge) {
    // 양방향 그래프기 때문
    graph[start].push(end);
    graph[end].push(start);
  }

  // 정점의 거리 기록
  const dist = Array(n + 1).fill(0);
  dist[1] = 1;

  // BFS
  const queue = new Queue();
  queue.enqueue(1);
  while (!queue.isEmpty()) {
    const src = queue.dequeue();
    for (const dest of graph[src]) {
      if (dist[dest] === 0) {
        queue.enqueue(dest);
        dist[dest] = dist[src] + 1;
      }
    }
  }
  const max = Math.max(...dist);

  return dist.filter((item) => item === max).length;
}

---

3. 다른 사람 풀이

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;
}

adjList
n = 6, edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

{
  '1': [ 3, 2 ],
  '2': [ 3, 1, 4, 5 ],
  '3': [ 6, 4, 2, 1 ],
  '4': [ 3, 2 ],
  '5': [ 2 ],
  '6': [ 3 ]
}