백준 1967 JS 풀이

구하는 값

트리의 지름이 가장 큰 값

핵심 아이디어

처음에는 각 노드마다 첫번째로 다른 노드 가능 경로에서 dfs를 돌며 가장 큰 값을 저장하고 그 값들이 2개 이상인 값들 중 내림차순 정렬을 하여 idx 0,1 인 값을 더해줬다.

답은 맞지만 시간초과가 발생하는데 모든 노드에서 다음 경로로 간 후 dfs를 돌기때문이다.

좀더 적은 순회로 지름을 찾는 방법이 필요했고 지름은 결국 leaf노드에서 leaf노드까지의 거리이기때문에

leaf노드들(인접리스트를 만들었을 때 길이가 1인 노드)을 따로 빼주고 leaf 노드들에서 dfs를 돌려 가장 큰 값을 저장했다.

시간 초과 코드

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

const n = Number(input[0]);

const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i < n; i++) {
    const [a, b, l] = input[i].split(" ").map(Number);
    graph[a].push([b, l]);
    graph[b].push([a, l]);
}
// console.log(graph);

const dfs = (cur, visited, select, sum) => {
    visited[cur] = true;

    for (const [next, dist] of graph[cur]) {
        if (!visited[next]) {
            dfs(next, visited, select, sum + dist);
        }
    }
    // console.log("sum", sum, cur);
    select.push(sum);
};

let max = 0;
for (let i = 1; i <= n; i++) {
    // console.log("i=========================================", i);
    const visited = new Array(n + 1).fill(false);
    const maxArr = [];
    visited[i] = true;
    for (const [next, dist] of graph[i]) {
        const select = [];
        dfs(next, visited, select, dist);
        maxArr.push(Math.max(...select));
    }

    // console.log(maxArr);
    if (maxArr.length >= 2) {
        maxArr.sort((a, b) => b - a);
        max = Math.max(maxArr[0] + maxArr[1], max);
    }
}

console.log(max);

통과 코드

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

const n = Number(input[0]);

const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i < n; i++) {
    const [a, b, l] = input[i].split(" ").map(Number);
    graph[a].push([b, l]);
    graph[b].push([a, l]);
}
// console.log(graph);

const leaf = [];
graph.forEach((v, node) => {
    if (v.length === 1) leaf.push(node);
});
// console.log(leaf);

const dfs = (cur, visited, select, sum) => {
    visited[cur] = true;

    if (graph[cur].length === 1) {
        select.push(sum);
        return;
    }

    for (const [next, dist] of graph[cur]) {
        if (!visited[next]) {
            dfs(next, visited, select, sum + dist);
        }
    }
    // console.log("sum", sum, cur);
};

let max = 0;
for (const i of leaf) {
    // console.log("i=========================================", i);
    const visited = new Array(n + 1).fill(false);

    visited[i] = true;
    for (const [next, dist] of graph[i]) {
        const select = [];
        dfs(next, visited, select, dist);
        max = Math.max(...select, max);
    }
}

console.log(max);

다른 사람풀이를 봤는데 더 간단한 풀이법이 있다. 모든 leaf노드를 탐색할 필요가 없다.

다른사람 코드

let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = Number(input[0]);
const g = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i < n; i++) {
    const [a, b, l] = input[i].split(" ").map(Number);
    g[a].push([b, l]);
}

let ans = 0;
function dfs(dn, w) {
    let tmp = [0, 0];
    for (let i = 0; i < g[dn].length; i++) {
        tmpChange(tmp, dfs(g[dn][i][0], g[dn][i][1]));
    }
    if (ans < tmp[0] + tmp[1]) ans = tmp[0] + tmp[1];
    return tmp[0] + w;
}

function tmpChange(od, nw) {
    if (od[0] < nw) {
        od[1] = od[0];
        od[0] = nw;
    } else {
        if (od[1] < nw) od[1] = nw;
    }
}

dfs(1, 0);
console.log(ans);

시간차이가 오지게 난다… 이게 뭐누..?

왜 시작점에서 가장 긴 노드를 찾고 그 노드에서 가장 멀리떨어져있는 노드까지의 거리가 지름이 되는걸까?

흐음..