목차
문제
트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.
이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.
트리의 노드는 1부터 n까지 번호가 매겨져 있다.
입력
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
예제
입력
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10
Plain Text
복사
출력
45
Plain Text
복사
풀이
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(input())
Tree = [[] for _ in range(N+1)]
# Tree 쌓기
for _ in range(N-1):
a, b, weight = map(int, input().split())
Tree[a].append([b,weight]) # Tree[Node]에 [연결된 node, weight] 형식으로 Tree를 쌓는다.
Tree[b].append([a,weight])
def dfs(start, before_wei):
for i in Tree[start]:
node, current_wei = i
if distance[node] == -1: # 아직 distance를 구하지 않았다면
distance[node] = before_wei + current_wei # before weight와 current weight를 더해서 distance를 구해줌
dfs(node, before_wei + current_wei) # node를 기준으로 다시 dfs 수헹
# root에서 가장 먼 점 y 찾기
distance = [-1]*(N+1)
distance[1] = 0
dfs(1, 0)
y = distance.index(max(distance))
# distance 초기화하고 y를 기준으로 distance 구하기
distance = [-1]*(N+1)
distance[y] = 0
dfs(y,0)
# y와 가장 먼 점과의 거리 구하기
print(max(distance))
Python
복사
트리의 지름을 구하는 알고리즘은
1.
임의의 점 를 잡는다. (일반적으로 루트를 잡음)
2.
에서 가장 먼 점 를 잡는다.
3.
에서 가장 먼 점 를 잡는다.
4.
가 트리의 지름.
특정한 정점에서 가장 거리가 먼 점은 dfs(depth-first-search) 방식을 통해서 구할 수 있다.
우선 두 개의 리스트가 필요하다.
•
트리의 정보를 담고 있는 리스트
•
특정한 정점과의 거리를 담고 있는 리스트
일반적인 트리와 다르게 여기서는 간선간의 거리 정보가 주어졌으므로 이를 반영하여 Tree list를 짜야한다.
그 다음에는 루트부터 시작해서 연결되어 있는 노드들을 확인하고 distance가 할당이 되어 있지 않은 경우 weight를 더해준다. 주의해야 하는 점은 깊어질수록 weight가 쌓이도록 설계해야 한다는 점이다.
예를 들어, 위의 예제에서 1과 2의 거리는 weight 정보인 3을 바로 더해주면 되지만, 1과 4의 거리는 1과 2 간의 거리에 2와 4 간의 weight를 더하는 방식으로 진행되어야 한다. 따라서 dfs를 바로 수행하는 것이 아니라 dfs의 두번째 인자에 weight를 추가해주어야 한다.
기억할 점
•
간선간의 정보를 담을 수 있는 Tree list의 형태를 기억하자.
•
트리의 지름 구하는 알고리즘 자체는 외워야 한다.