💻 백준 1967번: 트리의 지름

문제 소개 🧐

트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력 📝

  • 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다.
  • 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다.
  • 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다.
  • 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다.
  • 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

출력 📤

  • 첫째 줄에 트리의 지름을 출력한다.

제한 ❌

  • 시간 제한: 2초
  • 메모리 제한: 128MB

첫 번째 시도: DFS 🌳

Idea

  1. 임의의 노드에서 가장 먼 노드 찾기: 먼저, 트리 상의 임의의 노드(예: 1번 노드)에서 가장 먼 노드를 찾았다. 이 노드는 트리의 지름을 구성하는 두 노드 중 하나일 확률이 높다고 생각했다.
  2. 찾은 노드에서 가장 먼 노드까지의 거리 계산: 위에서 찾은 노드에서 다시 한번 가장 먼 노드를 찾았다. 이 두 노드 사이의 거리가 바로 트리의 지름이 될 것이라고 확신했다.

Code

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(node, dist):
    for next_node, next_dist in graph[node]:
        if visited[next_node] == -1:
            visited[next_node] = dist + next_dist
            dfs(next_node, dist + next_dist)

n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

visited = [-1] * (n + 1)
visited[1] = 0
dfs(1, 0)

start_node = visited.index(max(visited))
visited = [-1] * (n + 1)
visited[start_node] = 0
dfs(start_node, 0)

print(max(visited))

Result

  • 성공! 🎉
  • 메모리: 38680 KB
  • 시간: 104 ms
  • 와, 한번에 맞았다! 기분이 좋다. 😊

개선할 부분 🤔

  • 현재 코드는 DFS를 두 번 사용해서 트리의 지름을 구했다. 이 방법은 대부분의 경우에 잘 동작하지만, 트리의 구조에 따라 비효율적일 수도 있겠다.
  • 예를 들어, 트리가 한쪽으로 길게 늘어진 형태일 경우, 첫 번째 DFS에서 찾은 노드가 지름의 끝점이 아닐 수도 있다는 점을 고려해야겠다.
  • 하지만, 이 문제의 제약 조건 하에서는 현재 코드로도 충분히 해결 가능했다.