[백준] 1967 - 트리의 지름

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

문제 한줄 이해

- 트리가 있을 때 어떤 두 노드를 잡고 댕겼을때 가장 긴 지름 구하기

생각난 풀이

1번째 방법: 처음에는 가중치를 더해가면서 다익스트라를 응용하면 될거라 생각했다. 이유는 다익스트라 개념은 결국 최장거리 구하기 등의 이론이 들어가는데 여기서 낮은 값이 아닌 큰값을 더해가면서 거리를 계산하면 된다고 생각했다.

import sys
import heapq

n = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b, v = map(int, sys.stdin.readline().split())
    graph[a].append((b, v))
    graph[b].append((a, v))

def dijkstra(start):
    hq = []
    heapq.heappush(hq, (0, start))
    dis = [-1e9] * (n + 1)
    dis[start] = 0

    while hq:
        dist, nowv = heapq.heappop(hq)

        if dis[nowv] > dist:
            continue

        for i in graph[nowv]:
            if not visited[i[0]]:
                newdist = dist + i[1]
                if newdist > dis[i[0]]:
                    dis[i[0]] = newdist
                    heapq.heappush(hq, (newdist, i[0]))
                    visited[i[0]] = True

result = 0
for i in range(1, n + 1):
    dis = [-1e9] * (n + 1)
    visited = [False] * (n + 1)
    dijkstra(i)
    result = max(result, max(dis))

print(result)

하지만 시간초과가 발생했고 노드의 갯수가 최대 10000개로 시간복잡도에서 문제가 생긴것이다. 그래서 다른 방법을 고민해보다가 도저히 떠오르지 않아 검색을 해봤다.

 

2번째 방법: 검색을 통해 얻은 힌트는 바로 어떤 두 노드를 댕겨 늘여뜨렸을 때 어떤 임의의 노드에서 가장 거리가 먼 노드는 결국 가장 긴지름을 가지는 기준 노드가 된다. 

따라서 임의의 노드를 잡고 거리를 계산해 가장멀리 있는 기준 노드 둘중에 하나를 찾고 찾은 기준노드를 기준으로 가장 멀리 있는 노드를 찾아 결과값을 출력하면 된다.

따라서 dfs를 통해 처음 아무 노드를 기준으로 가장 먼 노드를 찾고 그 노드를 기준으로 거리가 가장 먼 값을 출력했다.

import sys
import heapq

n = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b, v = map(int, sys.stdin.readline().split())
    graph[a].append((b, v))
    graph[b].append((a, v))
    
def dfs(dist,start):
    global result
    global nowv
    visited[start] = True
    if result < dist:
        result = dist
        nowv = start
    for i in graph[start]:
        if visited[i[0]] == False:
            newdist = dist + i[1]
            dfs(newdist,i[0])

result = 0
nowv = 0
visited = [False] * (n+1)
dfs(0,1)
print(result,nowv)
visited = [False] * (n+1)
result = 0
dfs(0,nowv)
print(result,nowv)