문제
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));
}