[코테, 알고리즘] 백준 class 4 - 트리의 지름(트리에서 경로찾기)

별도의 알고리즘은 아닌데 이것저것 정리해볼 부분이 많은 문제라 글을 따로 뺐다.

[1967] 트리의 지름

[1167] 트리의 지름

---

그래프와 트리에서 경로찾기, BFS/DFS와 다익스트라

📈 그래프

그래프는 두 정점을 잇는 경로가 여러개 있을 수 있기 때문에 최단경로를 찾으려면 가중치에 따라 BFS나 다익스트라 중 골라 써야 한다.

• 모든 간선의 가중치가 동일할 때
  => BFS (시간복잡도 : O(V+E))
• 모든 간선의 가중치가 동일하지 않을 때
  => 다익스트라 (시간복잡도 : O(NlogN))

🌳 트리

트리는 두 정점을 잇는 경로가 유일하기 때문에 거리를 갱신하는 과정 자체가 없어서 (그냥 구한 경로가 곧 최단경로니까) 가중치의 유무에 상관없이 BFS/DFS로 (최단)경로를 찾을 수 있다.

cf) 다익스트라는 거리 갱신 과정이 있고 BFS/DFS는 방문여부만 확인한다.

• 가중치에 무관하게 BFS(DFS도 가능)

💡다익스트라와 BFS 모두 한 노드에 대해서 다른 모든 노드로 향하는 최단경로를 찾는다는 점에서 동일하기 때문에, 거리 갱신이 불필요한 트리에서 경로를 찾을 경우에는 시간복잡도가 짧은 BFS를 사용하는게 더 효율적이다.💡

트리의 지름

트리의 지름은 모든 경로 중에서 가장 먼 경로, 즉 가장 먼 정점 사이의 거리다.

구하는 방법은 정형화되어 있으니 외워두자.

1. 임의의 노드(x)에서 가장 먼 노드(y)를 찾는다.
2. 그 노드(y)에서 가장 먼 노드(z)를 또 찾는다.
3. 트리의 지름은 y와 z를 연결하는 경로다.

처음엔 모든 노드쌍에 대해 경로탐색을 해서 가장 큰 값을 찾았는데 메모리/시간초과가 났고, 이 방식대로 풀어야했다.

증명은 다른 블로그 참고

코드 (문제 1167)

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를 두번하는 방식으로 풀었다.