📚 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)

채점 결과

참고

• https://velog.io/@coding_egg/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC