[백준] 1240 노드사이의 거리 Node.js (BFS 풀이)

Janet·2023년 5월 23일
0

Algorithm

목록 보기
204/314

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

예제 입력 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1

2
7

문제풀이

✅ 답안 : BFS - Queue 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' ').map(Number));
const [N, M] = input.shift();
const request = input.splice(-M); // M개의 줄에 차례대로 입력받은 두 노드
const graph = [...Array(N + 1)].map(() => []);

// 무방향(양방향) 그래프 만들기
input.forEach(([from, to, distance]) => {
  graph[from].push([to, distance]);
  graph[to].push([from, distance]);
});

const bfs = (start, goal) => {
  const queue = [[start, 0]]; // [출발 정점, 깊이(거리) 초기값 0]
  const visited = Array(N + 1).fill(false); // 방문 체크할 배열

  while (queue.length) {
    const [curVertax, accDepth] = queue.shift(); // [현재 정점, 누적 깊이(거리)]

	// 현재의 출발 정점과 도착지였던 정점이 같아지면 누적된 깊이(거리) 반환
    if (curVertax == goal) return accDepth;

	// 현재 정점(graph[curVertax])과 [이어진 정점, 깊이(거리)]
    for (const [nextVertax, depth] of graph[curVertax]) {
      if (!visited[nextVertax]) {
        visited[nextVertax] = true; // 방문 처리
        queue.push([nextVertax, depth + accDepth]); // 큐에 이어진 정점 및 거리+누적 거리 담기
      }
    }
  }
};

for (const [from, to] of request) {
  console.log(bfs(from, to));
}
profile
😸

0개의 댓글