[JS] BFS, DFS - 가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

Question

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

 

 

Solution

step 1.

핵심 키워드 : 노드, 간선, 최단 경로

 

step 2.

최단 경로가 가장 큰 경우의 집합을 구하는 문제이다.

 

 

1. 먼저 그래프를 만든다.

정점이 1부터 시작하기때문에 편의상 배열을 0번부터 시작하지 않고 1번부터 시작하도록, 배열 크기를 n + 1로 정의한다.

인접 리스트이니깐 초기값으로 빈 배열을 넣어준다.

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

2. 간선들을 루프를 돌면서 그래프를 채워넣도록 하겠다.

출발지인 src에 도착지인 dest를 넣는다.

간선은 양방향이기 때문에 반대로도 넣어준다.

function solution(n, vertex) {
  const graph = Array.from(Array(n + 1), () => []);
  
  for (const [src, dest] of vertex) {
    graph[src].push(dest);
    graph[dest].push(src);
  }
}

3. 각 정점을 기록할 수 있도록 배열을 만든다.

위와 같이 정점만큼 배열을 만들어주고 0으로 초기화를 해준다.

첫 정점인 1번의 길이를 1이라고 하자.

function solution(n, vertex) {
  const graph = Array.from(Array(n + 1), () => []);
  
  for (const [src, dest] of vertex) {
    graph[src].push(dest);
    graph[dest].push(src);
  }
  
  const distance = Array(n + 1).fill(0);
  distance[1] = 1;
}

4. 간선들을 순회하기위해 BFS 로직을 작성한다.

BFS는 Queue를 이용하여 풀 수 있기때문에 Queue를 먼저 만들자.

일단은 배열을 이용해서 풀어보자.

function solution(n, vertex) {
  const graph = Array.from(Array(n + 1), () => []);
  
  for (const [src, dest] of vertex) {
    graph[src].push(dest);
    graph[dest].push(src);
  }
  
  const distance = Array(n + 1).fill(0);
  distance[1] = 1;
  
  // BFS
  const queue = [1];
}

5. queue의 길이가 0이 되지 전까지 루프를 돌린다.

먼저, 원점을 shift를 통해서 구한다.

 -> shift는 O(n)이라 성능이 좋지 않지만, 요소가 적을 경우에는 자바스크립트 엔진에서 최적화를 해준다.

출발지에서 목적지까지의 요소들을 다시 뽑아준다.

가지 않은 경로인 경우엔 초기값인 0이기 때문에, queue에 추가를 해준다.

그리고 도착지인 경로는 출발지인 경로에 + 1이 된다.

function solution(n, vertex) {
  const graph = Array.from(Array(n + 1), () => []);
  
  for (const [src, dest] of vertex) {
    graph[src].push(dest);
    graph[dest].push(src);
  }
  
  const distance = Array(n + 1).fill(0);
  distance[1] = 1;
  
  // BFS
  const queue = [1];
  while (queue.length > 0) {
    const src = queue.shift();
    for (const dest of graph[src]) {
      if (distance[dest] === 0) {
        queue.push(dest);
        distance[dest] = distance[src] + 1;
      }
    }
  }
}

6. 마지막으로 거리들 중 가장 큰 값을 뽑아낸다.

그리고 최대값과 같은 값을 가진 것이 몇개인지 알아내고 그 값을 리턴해 준다.

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

 

---

Queue class를 이용한 풀이

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 += 1;
    return value;
  }
  
  isEmpty() {
    return this.rear === this.front
  }
}

function solution(n, vertex) {
  const graph = Array.from(Array(n + 1), () => []);
  
  for (const [src, dest] of vertex) {
    graph[src].push(dest);
    graph[dest].push(src);
  }
  
  const distance = Array(n + 1).fill(0);
  distance[1] = 1;
  
  // BFS
  const queue = new Queue();
  queue.enqueue(1);
  while (!queue.isEmpty()) {
    const src = queue.dequeue();
    for (const dest of graph[src]) {
      if (distance[dest] === 0) {
        queue.enqueue(dest);
        distance[dest] = distance[src] + 1;
      } 
    }
  }
  
  const max = Math.max(...distance);
  
  return distance.filter(item => item === max).length;
}

 

 

 

n이 작은 경우는 shift를 이용한 풀이가 좋지만 n이 크다면 JS 엔진에서 최적화를 못해주므로 성능이 좋지 않다.

그러므로 n이 큰 경우에는 Queue를 직접 구현해서 사용하는 것이 좋다.