트리의 지름 ( 1167번 )

1167번: 트리의 지름

 

---

🧠 알고리즘

• 트리에서 지름 계산 (DFS 2회)

 

✔️ 동작 방식

• 문제 핵심 아이디어
  
  • 트리의 지름은 가장 먼 두 노드 간 거리를 의미하며, DFS를 두 번 수행하면 구할 수 있다.

1. 첫 번쨰 DFS
   
   • 임의 노드에서 DFS 수행
   • 모든 경로의 누적 비용 계산 → 가장 먼 노드를 찾음 ( far_node )
2. 두 번쨰 DFS
   
   • 첫 번쨰 DFS로 찾은 far_node에서 DFS 수행
   • 다시 모든 경로의 누적 비용을 계산 → 가장 먼 노드까지의 거리가 트리 지름 ( far_len )
3. DFS 동작 요약
   
   • 재귀로 각 노드를 방문해 부모 노드를 제외한 연결 노드 탐색
   • 각 경로의 누적 비용을 계산
   • 최대 거리 갱신 시 해당 노드와 거리를 저장

---

 

🧾 코드

import sys
sys.setrecursionlimit(10 ** 6)

def _dfs(node, parents, cost):
    answer_node, answer_len = node, cost

    for next_node, next_cost in conn[node]:
        if next_node != parents:
            max_node, max_len = _dfs(next_node, node, cost + next_cost)

            if max_len > answer_len:
                answer_node, answer_len = max_node, max_len
    
    return answer_node, answer_len


v = int(sys.stdin.readline().rstrip())
conn = [[] for _ in range(v + 1)]
for _ in range(v):
    info = tuple(map(int, sys.stdin.readline().rstrip().split()))
    for idx in range(1, len(info) - 1, 2):
        conn[info[0]].append((info[idx], info[idx + 1]))

far_node, far_len = _dfs(1, -1, 0)
far_node, far_len = _dfs(far_node, -1, 0)
print(far_len)

---

 

⏱️ 시간 복잡도

_dfs(node, parents, cost) : DFS 알고리즘, 모든 노드를 한 번씩 방문하므로 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )

---