백준 1167번 트리의 지름

서론

1167번: 트리의 지름
1967번: 트리의 지름

트리의 지름을 구하는 문제입니다. 트리를 탐색하는 문제는 이제 쉽게 해결하는데 갑자기 지름을 구하라고 해서 어려웠습니다. 트리의 지름을 구하는 개념을 찾아 보고 풀었습니다.

제한 조건

• 시간제한 - 2초

시간제한은 2초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 트리를 탐색하는 데 DFS를 사용하기 때문에 시간복잡도 O(V+E)를 가지고 문제에서 V=100,000개이기 때문에 시간제한은 충분합니다. 위에서 적은 알고리즘을 쓰면 깔끔하게 풀리는데 만약에 다른 식으로 지름을 구하려고 하면 시간이 더 걸릴 수도 있을 것 같습니다.

• 메모리 제한 - 256MB

메모리 제한은 256MB입니다. 앞선 문제들에서 말했다시피 대부분 문제가 주어진 정보를 선언하는 데는 문제가 없습니다. 이문제에서는 DFS를 사용하니까 que에 데이터가 무한하게 쌓지 않게만 제어하면 됩니다. 사실 무한하게 쌓이면 문제 자체가 풀리지도 않습니다.

트리의 지름(DFS)

트리의 지름을 구하는 개념만 알고 있으면 트리 탐색을 두 번 실행해서 풀 수 있습니다.

1. 임의의 노드를 기준으로 가장 멀리 떨어진 노드를 구한다.
2. 그 노드로부터 가장 멀리 떨어진 노드를 구한다.
3. 2번에서 구한 거리가 트리의 지름이다.

그래서 1번 노드를 기준으로 DFS를 한번 사용하여 가장 멀리 떨어진 노드를 구하고 거기서 또 DFS를 사용하여 가장 멀리 떨어진 노드와의 거리를 구했습니다.

import sys
from collections import deque as dq
input = sys.stdin.readline

V = int(input())


def make_graph():
    graph = {}
    for i in range(1, V+1):
        graph[i] = []
    for _ in range(V):
        edge_list = list(map(int, input().split()))
        vertex = edge_list[0]
        edge_list = edge_list[1:]

        for i in range(len(edge_list)-1):
            if i % 2 != 0:
                continue
            graph[vertex].append([edge_list[i], edge_list[i+1]])
    return graph


def DFS(graph, start):
    que = dq()
    que.append(start)

    visited = [False]*(V+1)
    visited[start] = True

    path = [0]*(V+1)
    path[start] = 0

    while que:
        base_v = que.pop()
        for next_v, weight in graph[base_v]:
            if not visited[next_v]:
                path[next_v] = path[base_v]+weight
                que.append(next_v)
                visited[next_v] = True

    return max(path), path.index(max(path))


graph = make_graph()
path = DFS(graph, 1)
path2 = DFS(graph, path[1])
print(path2[0])

생각