[DFS] 노드 사이의 거리

[ericagong]

⭐ 성찰

1. 성찰내용
2. 성찰내용
3. 성찰내용

❓ 문제 상황

노드 사이의 거리

👨‍💻 문제 해결: 풀이 방식

✅ 1차 풀이: 키워드

1. 풀이흐름
2. 풀이 흐름
3. 풀이흐름

   
   // https://www.acmicpc.net/problem/1240

const fs = require("fs"); const inputs = fs.readFileSync("/dev/stdin").toString().split("\n");

const [N, M] = inputs.shift().split(" ").map(Number); const g = Array.from({ length: N + 1 }, () => new Array()); for (let i = 0; i < N - 1; i++) { const [n1, n2, dis] = inputs.shift().split(" ").map(Number); g[n1].push([n2, dis]); g[n2].push([n1, dis]); }

let v = new Array(N + 1).fill(false); let cd = 0; function dfs(cn, en) { v[cn] = true;

// 특정 노드 도달 시 dfs 종료 if (cn === en) { console.log(cd); return; }

for (const [n, d] of g[cn]) { if (v[n]) continue; cd += d; v[n] = true; dfs(n, en); cd -= d; v[n] = false; } }

for (let i = 0; i < M; i++) { const [n1, n2] = inputs.shift().split(" ").map(Number);

// 매 쿼리마다 정보 초기화 필요 cd = 0; v = new Array(N + 1).fill(false);

dfs(n1, n2); }