1167 - 트리의 지름
📚 1167 - 트리의 지름
이해
📣 트리의 지름 구하기 공식
(1) 시작 노드에서 가장 먼 노드를 찾는다. (가장 먼 노드 : a)
(2) a에서 가장 먼 노드를 찾는다. (a에서 가장 먼 노드 : b)
(3) a - b가 트리의 지름이 된다.
1167문제와 거의 유사한 문제지만, 시작 노드가 정해지지 않았다.
dfs
로 풀어도되지만, 시작 노드를 모르니 전체 방문한다는 가정하에 bfs
를 이용하여 풀었다.
트리 지름 : 가장 긴 것 (bfs
)
def bfs(start):
visited = [-1] * (v + 1)
queue = deque()
queue.append(start)
visited[start] = 0
# 거리, 노드
_max = [0, 0]
while queue:
c = queue.popleft()
# e: 노드, wei : 거리
for e, wei in graph[c]:
if visited[e] == -1:
visited[e] = visited[c] + wei # 현재 c를 기준, 시작 노드에서 c까지 거리 + (노드 c에서 노드 d까지 거리)
queue.append(e) # 현재 노드 저장
# 방문한 노드라면, 길이를 잰다.
if _max[0] < visited[e]:
_max = visited[e], e
return _max
_max
에는 거리와 노드가 저장된다.- 현재 노드에서 다른 곳에 방문한 노드라면, 현재 노드까지 거리 + 현재 노드에서 방문한 곳 노드까지 거리를 해준다.
- 만약, 노드를 방문했다면 길이를 잰다.
- 저장되어 있던 길이보다 더 길다면 업데이트 한다.
- 첫 번째
bfs
결과로 가장 먼 노드를 찾았다면, 해당 노드가 두 번째bfs
의 시작 노드가 된다. - 두 번째
bfs
시작 노드를 통해 가장 먼 곳에 있는 노드와의 거리를 구한다.
소스
from sys import stdin
from collections import deque
read = stdin.readline
v = int(read())
graph = [[] for _ in range(v + 1)]
for _ in range(v):
c = list(map(int, read().split()))
for e in range(1, len(c) - 2, 2):
graph[c[0]].append((c[e], c[e + 1]))
def bfs(start):
visited = [-1] * (v + 1)
queue = deque()
queue.append(start)
visited[start] = 0
# 거리, 노드
_max = [0, 0]
while queue:
c = queue.popleft()
# e: 노드, wei : 거리
for e, wei in graph[c]:
if visited[e] == -1:
visited[e] = visited[c] + wei # 현재 c를 기준, 시작 노드에서 c까지 거리 + (노드 c에서 노드 d까지 거리)
queue.append(e) # 현재 노드 저장
# 방문한 노드라면, 길이를 잰다.
if _max[0] < visited[e]:
_max = visited[e], e
return _max
distance, node = bfs(1)
distance, node = bfs(node)
print(distance)
채점 결과
참고
Author And Source
이 문제에 관하여(1167 - 트리의 지름), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/1167-트리의-지름저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)