별도의 알고리즘은 아닌데 이것저것 정리해볼 부분이 많은 문제라 글을 따로 뺐다.
그래프는 두 정점을 잇는 경로가 여러개 있을 수 있기 때문에 최단경로를 찾으려면 가중치에 따라 BFS나 다익스트라 중 골라 써야 한다.
트리는 두 정점을 잇는 경로가 유일하기 때문에 거리를 갱신하는 과정 자체가 없어서 (그냥 구한 경로가 곧 최단경로니까) 가중치의 유무에 상관없이 BFS/DFS로 (최단)경로를 찾을 수 있다.
cf) 다익스트라는 거리 갱신 과정이 있고 BFS/DFS는 방문여부만 확인한다.
💡다익스트라와 BFS 모두 한 노드에 대해서 다른 모든 노드로 향하는 최단경로를 찾는다는 점에서 동일하기 때문에, 거리 갱신이 불필요한 트리에서 경로를 찾을 경우에는 시간복잡도가 짧은 BFS를 사용하는게 더 효율적이다.💡
트리의 지름은 모든 경로 중에서 가장 먼 경로, 즉 가장 먼 정점 사이의 거리다.
구하는 방법은 정형화되어 있으니 외워두자.
x
)에서 가장 먼 노드(y
)를 찾는다.y
)에서 가장 먼 노드(z
)를 또 찾는다.y
와 z
를 연결하는 경로다.처음엔 모든 노드쌍에 대해 경로탐색을 해서 가장 큰 값을 찾았는데 메모리/시간초과가 났고, 이 방식대로 풀어야했다.
from collections import deque
V = int(input())
tree = [[] for _ in range(V+1)]
for _ in range(V):
edges = list(map(int, input().split()))
node = edges[0]
for i in range(1, len(edges)-2, 2):
tree[node].append((edges[i], edges[i+1]))
queue = deque([(1,0)])
visited = [False] * (V+1)
visited[1] = True
max = [-1, -1]
for _ in range(2):
while queue:
now, dist = queue.popleft()
if dist > max[1]:
max[0] = now
max[1] = dist
for next, weight in tree[now]:
if not visited[next]:
queue.append((next, dist+weight))
visited[next] = True
queue.append((max[0], 0))
visited = [False] * (V+1)
visited[max[0]] = True
print(max[1])
다른 사람들은 DFS로 많이 푸는거 같은데 나는 BFS를 두번하는 방식으로 풀었다.