트리에서 가장 긴 신호 지연 찾기
자바스크립트 코딩테스트 문제로 tree-diameter 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
가중치가 있는 트리 형태의 통신망에서, 신호가 가장 오래 걸리는 두 장비 사이의 지연 시간을 구하세요.
문제 설명
장비 n개가 0번부터 n - 1번까지 번호가 붙어 있습니다. 두 장비를 연결하는 케이블 정보 edges가 주어지며, 각 원소는 [a, b, delay] 형태입니다.
통신망은 트리입니다. 즉, 모든 장비가 연결되어 있고 사이클이 없습니다. 두 장비 사이의 신호 지연 시간은 그 둘을 잇는 유일한 경로에 포함된 delay의 합입니다.
서로 다른 두 장비 사이에서 만들 수 있는 신호 지연 시간 중 최댓값을 반환하는 longestSignalDelayInTree 함수를 작성하세요. 장비가 하나뿐이면 이동할 수 있는 다른 장비가 없으므로 0을 반환합니다.
제한사항
1 <= n <= 100,000edges.length === n - 1- 각 간선은
[a, b, delay]형태입니다. 0 <= a, b < na !== b1 <= delay <= 1,000,000- 입력으로 주어지는 그래프는 항상 연결된 트리입니다.
- 반환값은 가장 긴 경로의 지연 시간입니다.
예시
- 입력:
n = 5,edges = [[0, 1, 3], [1, 2, 4], [1, 3, 2], [3, 4, 6]]→ 출력:12 - 입력:
n = 1,edges = []→ 출력:0 - 입력:
n = 4,edges = [[0, 1, 2], [1, 2, 3], [2, 3, 5]]→ 출력:10 - 입력:
n = 6,edges = [[0, 1, 7], [0, 2, 4], [0, 3, 9], [0, 4, 1], [0, 5, 6]]→ 출력:16
힌트
- 트리에서는 어떤 두 노드 사이의 경로가 정확히 하나만 존재합니다.
- 임의의 노드에서 가장 먼 노드를 찾으면, 그 노드는 가장 긴 경로의 한쪽 끝점이 됩니다.
- 그 끝점에서 다시 가장 먼 노드까지의 거리가 트리의 지름입니다.
해설
이 문제는 트리의 지름을 구하는 전형적인 문제입니다. 트리의 지름은 트리 안에서 가장 긴 단순 경로의 길이를 뜻합니다.
모든 노드 쌍의 거리를 직접 계산하면 노드 수가 클 때 너무 느립니다. 대신 트리의 성질을 이용하면 탐색을 두 번만 해도 됩니다.
풀이 흐름은 다음과 같습니다.
- 간선 목록으로 양방향 인접 리스트를 만듭니다.
- 임의의 시작점, 예를 들어
0번 노드에서 가장 먼 노드far를 찾습니다. far에서 다시 한 번 탐색해 가장 먼 거리diameter를 찾습니다.diameter를 반환합니다.
왜 이 방식이 맞을까요? 트리에서 임의의 노드로부터 가장 먼 노드는 어떤 최장 경로의 한쪽 끝점이 됩니다. 따라서 그 끝점에서 다시 가장 먼 곳까지의 거리를 구하면 전체 트리에서 가능한 가장 긴 경로를 얻을 수 있습니다.
가중치가 모두 양수이고 그래프가 트리이므로 다익스트라가 필요하지 않습니다. 각 노드까지 가는 경로가 하나뿐이라, 부모 노드로 되돌아가는 것만 피하면서 거리 합을 누적하면 됩니다.
재귀 DFS는 n이 클 때 호출 스택 제한에 걸릴 수 있으므로 JavaScript에서는 스택 배열을 직접 쓰는 반복 DFS가 안전합니다.
시간 복잡도는 인접 리스트 생성과 두 번의 탐색을 합쳐 O(n)입니다. 인접 리스트와 탐색 스택을 사용하므로 공간 복잡도도 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.