백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1167 트리의 지름 [트리, 그래프, DFS]

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1167 트리의 지름 [트리, 그래프, DFS]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

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

1167번: 트리의 지름

 

 

 

 

 

문제풀이 소감 🧑‍💻

이전 문제 1967 문제와 같이 DFS 를 두번 돌려서 트리의 지름을 구하는 방법으로 풀었어요.

1967을 먼저 학습하고 온 덕분에 수월하게 풀렸지만, DFS 를 두 번 돌려서 트리의 지름을 구할 수 있다는 발상 자체가 난이도 있다고 생각합니다. 이 사전 지식이 있느냐 없느냐에 따라 체감 난이도가 확 달라질 것 같아요.

 

참고로 1967 문제는 브루트포스로도 풀렸지만, 이번 문제는 그렇게 풀리지 않기 때문에 더 높은 등급으로 측정된 것 같습니다.

 

 

 

요구사항 📋

노드들을 서로 이어서 경로에 있는 가중치들을 합할 때, 가장 큰 가중치의 합을 나타나내는 경우를 출력하시오.

한 노드에 연결된 경로는 여러개일 수 있다.

 

 

주의 ❗

이번에는 각 노드에 연결된 경로가 무조건 한 개가 아닌 여러개 일 수 있습니다.

이 처리를 받아주는 부분이 1967 문제와의 차이입니다.

 

 

 

해결 전략 📝

우선, 트리의 정보가 담긴 입력들을 가지고 트리를 만든다.

 

두번째 DFS 를 돌릴 때, 부모노드로 거슬러 올라가야하므로 양방향으로 트리를 만들어준다.

 

이후 루트노드인 1에서부터 각 자식 노드들까지 길이를 DFS 로 탐색하면서 구해준다.

 

탐색이 마쳤다면, 길이가 저장된 값들 중에 가장 큰 값을 가진 Index 가 최장 길이를 가지고 있는 노드중 한쪽이다.

 

다시 이 노드부터 시작해서 모든 노드를 탐색하여 해당 위치에서 가장 먼거리에 위치한 노드를 찾는다.

 

이때는 리프노드가 시작이므로 부모노드, 부모노드의 자식노드들을 모두 탐색하면서 가중치를 계산한다.

 

최종적으로 거리에 담긴 가장 큰 값이 트리의 지름 값이다.

 

 

 

 

정답 💯

 

 

 

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

const input_N = input.shift();
const [...input_treeInfo] = input.map((v) => v.split(" ").map(Number));

function solution(N, treeInfo) {
  const dfs = (node, weight) => {
    tree[node].forEach((v) => {
      if (dist[v[0]] === -1) {
        dist[v[0]] = weight + v[1];
        dfs(v[0], dist[v[0]]);
      }
    });
  };

  const tree = Array.from({ length: N + 1 }, () => []);
  treeInfo.forEach((info) => {
    const parent = info[0];
    for (let i = 1; i < +(info.length / 2); i++) {
      const child = info[2 * i - 1];
      const weight = info[2 * i];
      tree[parent].push([child, weight]);
      tree[child].push([parent, weight]);
    }
  });

  let dist = Array.from({ length: N + 1 }).fill(-1);
  dist[1] = 0;
  dfs(1, 0);

  let maxIdx = 0;
  let maxV = 0;
  dist.forEach((v, i) => {
    if (v > maxV) {
      maxV = v;
      maxIdx = i;
    }
  });

  dist = Array.from({ length: N + 1 }).fill(-1);
  dist[maxIdx] = 0;
  dfs(maxIdx, 0);

  const answer = Math.max(...dist);

  return answer;
}

console.log(solution(+input_N, input_treeInfo));