알고리즘 연습하기 - DFS를 활용한 트리

알고리즘 문제를 풀다보면 트리 관련해서 이진 트리 혹은 이진 트리 순회 문제도 많이 확인할 수 있지만 그래프의 지름을 구하는 문제도 종종 확인할 수 있다.

🎯 트리의 지름

트리의 지름 문제는 간략하게 설명하자면 하나의 노드부터 가장 멀리 떨어져있는 노드의 거리를 계산하는 문제이다. 하지만 가장 멀리 떨어져있다고 해서 트리의 leaf를 의미하는 것은 아니다. 보통 간선의 가중치를 알려주기 때문에 하나의 노드에서부터 연결된 모든 노드의 가중치의 합이 가장 큰 값이 해당 트리의 지름인 셈이다.

결과적으로 트리도 그래프와 같이 DFS를 활용하여 최대한 갈 수 있을만큼 가며 가중치를 계산하는 방식으로 구하면 된다. 단, BFS는 최단 거리를 구할 때 많이 사용되기 때문에 이 문제에서는 DFS를 이용해야 한다.

모든 노드를 반복문을 이용하여 순회하는 것은 시간초과가 발생할 확률이 높다. 아니 거의 100% 시간초과가 발생한다. 여기서 1번 노드부터 가장 가중치가 큰 노드까지를 우선적으로 계산하고, 해당 노드에서부터 DFS를 진행하게 된다면 가장 긴 트리의 지름을 구할 수 있게된다.

따라서 단순히 가중치만 계산하는 것이 아니라 노드의 번호까지 입력을 해줘야 코드가 정상적으로 작동이 된다.

🎯 해결 코드

let visited = Array(N + 1).fill(false);
let max = { node: 0, dist: 0 };

function DFS(node, dist) {
  visited[node] = true;
  if (max.dist < dist) max = { node, dist };
  for (const [nextDist, nextNode] of graph[node]) {
    if (visited[nextNode]) continue;
    DFS(nextNode, dist + nextDist);
  }
}

DFS(1, 0);
visited.fill(false);
DFS(max.node, 0);
console.log(max.dist);

🎯 트리의 지름
🎯 해결 코드