[문제 풀이] 백준 1167

해결 과정

처음에는 모든 Edge를 다 돌며 탐색하도록 했더니 시간 초과가 났다. 연결되어 있는 Edge가 1개인 경우만 돌며 탐색해도 4%에서 시간초과가 났다. 다른 방법이 있겠구나 찾아보니 트리에서 지름을 구하는 방법이 있었다.

 

나의 풀이

from collections import deque

V = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(V):
    infoList = list(map(int, input().split()))
    vertex = infoList[0]
    edges = infoList[1:-1]
    for a, b in zip(edges[0::2], edges[1::2]):
        graph[vertex].append((a, b))

def bfs(start):
    distance = [-1] * (V+1)
    queue = deque([start])
    distance[start] = 0
    distanceAndEdge = [0, 0]

    while queue:
        cur = queue.popleft()
        for a, b in graph[cur]:
            if distance[a] == -1:
                distance[a] = distance[cur] + b
                queue.append(a)
                if distanceAndEdge[0] < distance[a]:
                    distanceAndEdge = [distance[a], a]

    return distanceAndEdge

dis, node = bfs(1)
dis, node = bfs(node)
print(dis)

 

다른 풀이

참고했음.

 

IDEA

트리에서 지름을 구하는 문제. 모든 Edge를 다 돌며 탐색하면 시간초과가 나도록 설계되어 있는 문제이다. 찾아보니 트리에서 최대 지름을 찾는 과정이 있었다. 

 

1) 임의의 한 Edge에서 가장 먼 Edge를 찾는다.

2) 1)에서 찾은 먼 Edge에서 가장 먼 Edge 사이가 곧 최대 지름이다.