이 문제는 그림을 보면 이해가 빨라진다.
우리는 각 노드를 쫙 잡아당겼을때 길이가 가장 길어지도록 하는 길이를 찾아야 한다.
만약 오른쪽 그림이 가장 길게 잡아당겨진 형태라고 가정한다.
그럼 오른쪽에 회색 노드들 중에서 아무거나 잡고 DFS를 통해 가장 먼 노드를 찾으면 그건 무조건 파란색 노드가 된다.
신기하게도 어떤 노드를 택하던 가장 먼 노드를 찾으면 그건 파란색 노드가 되는것이다. 진짜 신기하다.
그렇게 파란색 노드를 하나 찾고, 이번에 찾은 파란색 노드로부터 가장 먼 길이를 찾으면 우리가 찾고자하는 트리의 길이가 된다......
그럼 DFS를 단 2번만 하면 해결되는 문제이다.
그럼 DFS할 때 각 길이만 저장하면서 확인하면 되는 것이다.
1. DFS(1)로 파란색 노드하나 찾기
2. DFS(BlueNode)로 반대쪽 파란색 노드 찾으며 길이구하기
3. 길이 출력
import sys
input = sys.stdin.readline
n = int(input())
M =[[]for i in range(n+1)]
for i in range(n-1):
a,b,c = map(int, input().split())
M[a].append([b,c])
M[b].append([a,c])
def DFS(node):
s = [[node,0]]
visited = [0 for i in range(n+1)]
big = 0
leaf = 0
while s:
node,length = s.pop()
visited[node] = 1
nodelist = M[node]
if len(nodelist) == 1: #leaf노드일경우 length를 big와 비교
if length > big:
big = length
leaf = node
for node in nodelist:
if visited[node[0]] == 0:
s.append([node[0],node[1]+length])
return leaf, big
node,legth = DFS(1)
node,legth = DFS(node)
print(legth)
처음에는 이해가 안가서 왜 DFS를 써야하는지 몰랐는데 그림을 보고 팀원의 설명을 들으니 한번에 이해가 갔다. 진짜 신기한 문제다.
'알고리즘' 카테고리의 다른 글
[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드) (0) | 2021.08.02 |
---|---|
[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드) (0) | 2021.07.26 |
[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP) (0) | 2021.07.26 |
[py3] 백준 2573 풀이 (빙산, DFS, 그래프) (0) | 2021.07.24 |
[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법) (0) | 2021.07.22 |