트리의 지름
문제
트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.
이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.
트리의 노드는 1부터 n까지 번호가 매겨져 있다.
입력
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
예제 입력 1
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10예제 출력 1
45문제 해석
트리에 가중치가 붙어있어서 흔히 다익스트라나 플로이드 워셜 문제로 헷갈릴 수가 있다. 하지만
"그래프일 경우"
간선의 가중치가 모두 동일 -> BFS
그렇지 않은 경우 -> 다익스트라
"트리인 경우"
DFS or BFS
유의하도록 하자.
필자는 이 사실을 모르고 보자마자 바로 플로이드 워셜로 풀었다.
답은 나오지만 메모리 초과가 발생한다.
심지어 플로이드 워셜의 시간 복잡도는 O(n^3)이다. 문제에서 입력값의 범위는 10000개가 최대라고 하였는데, 10000개는 보통 O(n^2)의 시간 복잡도를 가지는 알고리즘을 이용하여 풀어야 한다.
그렇다면 또 하나의 의문이 생길 수 있다.
다익스트라를 이용하여 풀면 되지 않을까?
다익스트라의 시간 복잡도는 O(nlogn)이기에 적합하다고 생각할 수 있다.
맞다. 다익스트라로도 풀 수 있다. 조금있다가 문제 풀이에서 보여줄 것이지만 풀 수는 있다.
하지만 이 문제는 특별 케이스이다.
만약 다익스트라로 접근을 한다면 보통 플로이드 워셜처럼 모든 노드에서 갈 수 있는 최대 경로나 최단 경로를 구해야 한다. 그렇다면 시간 복잡도는 O(n^2logn)이기 때문에 시간초과가 뜬다.
이 문제에서는 굳이 n개의 노드를 전부 다익스트라를 사용하지 않아도 되므로 통과하기는 한다. 하지만 트리에서 가중치가 되어있으면 dfs나 bfs로 접근하도록 하자.
풀이1 (플로이드 워셜)
- 플로이드 워셜은 a 노드에서 b 노드까지 갈 수 있는 최단 경로들을 2차원으로 정리한 알고리즘이다.
- 하지만 문제는 최대 지름을 찾는 문제인데 왜 플로이드 워셜을 쓰냐 라고 생각할 수 있다.
- 어차피 트리 문제이다.
- 트리는 그래프 처럼 여러 곳으로 뻗쳐있지 않고 연결이 많아봤자 자식노드 2개이다.
- 1번 노드에서 8번 노드까지 가는데 걸리는 최소 경로를 트리에 접합을 시켜보자
- 어차피 트리는 어딘가를 꼬아서 가지 않고 한쪽 방향으로 쭉 내려간다.
- min 값으로 구해도 같은 값이 나오기 때문에 아무 문제 없다.
- N + 1 * N + 1 개의 2차원 배열을 선언해준다.
- 자기 자신으로 가는 값은 0이기 때문에 0으로 초기화를 시켜준다.
- 입력값들을 받아서 a 노드에서 b 노드로 가는데 c 만큼 걸리는 걸 2차원 배열에 집어넣어준다.
- 어차피 각 노드들을 방문하지 않았기 때문에 각 노드로 가는 경로 값은 INF 값이다.
- 그래서 k를 거쳐 가는 것을 루프를 돌려서 최솟값을 graph에 넣어준다.
- 그렇게 하면 한번에 노드들을 거쳐서 갈 수 있는 노드가 아닌 이상 min 값으로 업데이트 될 일이 없다.
- 무슨 말이냐면 오른쪽 노드로 갔다가 다시 갔던 길을 리턴해서 오는 경우가 없다는 얘기다. 어차피 min값을 저장해주기 때문에 결국 graph에 저장되는 값들은 전부 한번에 갈 수 있는 경우만이다.
- 최단 경로, 즉 트리들이 한번에 a노드에서 b노드로 갈 수 있는 거리들이 전부 2차원 배열에 업데이트가 된다.
import sys
N = int(sys.stdin.readline())
INF = 10 ** 9
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
if i == j:
graph[i][j] = 0
for i in range(N - 1):
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
graph[b][a] = c
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
max_list = []
max_val = 0
for i in range(1, N + 1):
for j in graph[i]:
if j == INF:
continue
else:
if max_val < j:
max_val = j
max_list.append(max_val)
max_val = 0
print(max(max_list))- 하지만 위에서 말했듯이 플로이드 워셜은 O(n^3)의 시간복잡도를 가지고 있으므로 해당 문제에 적합하지 않은 알고리즘이다.
풀이2 (dfs)
- 이번에는 dfs이다. 플로이드 워셜에서는 각 노드들이 갈 수 있는 모든 경로들의 가중치들을 뽑아낼 수 있었지만, dfs는 시작 노드에서 모든 노드들을 끝까지 탐색하면서 시작 노드와 얼마나 거리가 떨어졌는지만 알 수 있다.
- 그래서 생각해 낸 것이 1번 노드를 시작으로 dfs를 돌려서 전부다 탐색하고 나면 1번 노드와 가장 먼 거리에 있는 노드를 찾아서 그것을 시작 노드로 다시 dfs를 돌리는 것이다.
- 사실 어떤 노드를 기준으로 시작하냐는 중요한 것이 아니다.
- 어떤 임의의 노드를 시작점으로 그 노드와 가장 먼 지점의 노드를 찾아내서 그 노드를 다시 시작점으로 가장 먼 지점의 노드를 찾아내면 최대 지름이 된다는 얘기이다.
- 여기서 가장 큰 값을 뽑아내면 그것이 최대 지름이 된다.
- 첫 노드 시작점에서 가장 긴 거리가 나올 수도 있고, 두번째에 나올 수도 있다.
- 왜 굳이 2번이냐면 3번부터는 계속해서 최대 경로 값이 나오기 때문이다.
import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
graph = [[] for _ in range(N + 1)]
for i in range(1, N):
a, b, c = map(int, sys.stdin.readline().split())
graph[a].append([b, c])
graph[b].append([a, c])
distance = [-1] * (N + 1)
distance[1] = 0
def dfs(start, dis):
for i in range(len(graph[start])):
next, next_dis = graph[start][i]
if distance[next] == -1:
distance[next] = next_dis + dis
dfs(next, distance[next])
dfs(1, 0)
max_index = distance.index(max(distance))
distance = [-1] * (N + 1)
distance[max_index] = 0
dfs(max_index, 0)
print(max(distance))풀이3 (다익스트라)
- 사실 dfs와 푸는 방식이 크게 다르지 않다.
- dfs에서는 깊이 탐색으로 노드 전부를 재귀 호출을 이용해 탐색을 했다면, 다익스트라는 최소 힙을 이용하여 가장 min한 최단 경로를 찾아서 특정 노드에서 여러 노드까지의 거리들을 업데이트 해준다.
- 플로이드 워셜에서 설명했듯이 트리에서는 min 값으로 업데이트 하는 것이 각 노드 사이의 거리이다. 굳이 다른 노드들을 거쳐서 갈 필요가 없기 때문이다.
- 그렇게 출발 노드가 갈 수 있는 최단 경로들을 뽑은 후, dfs에서 했던 것처럼 출발 노드와 가장 거리가 먼 노드를 다시 출발노드로 해서 다익스트라 함수를 다시 호출해준다.
- 그렇게 되면 queue에 저장된 값들 중 가장 큰 값이 최대 지름이 된다.
import sys
import heapq
INF = int(1e9)
N = int(sys.stdin.readline())
graph = [[] for i in range(N + 1)]
visited = [False] * (N + 1)
distance = [INF] * (N + 1)
for _ in range(N - 1):
a, b, c = map(int, sys.stdin.readline().split())
graph[a].append((b, c))
graph[b].append((a, c))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(1)
distance[0] = -1
new_start = distance.index(max(distance))
distance = [INF] * (N + 1)
visited = [False] * (N + 1)
dijkstra(new_start)
distance[0] = -1
print(max(distance))다익스트라
- distance를 노드 갯수에 맞게 INF로 초기화
- 0과 출발 노드를 heappush를 이용해 queue에 넣어줌
- distance[start] = 0으로 만들어줌 자기 자신한테는 못와서
- 그렇게 queue가 빌때까지 루프를 돔
- heappop()을 이용하여 dist와 now를 뽑아줌.
- 여기서 dist는 출발 노드에서 now까지 갈 수 있는 거리 - distancee[now]가 dist보다 작으면 업데이트 할 필요 없으니
- continue - 그게 아니면
- now 노드가 갈 수 있는 노드들을 탐색한다.
- cost 변수에 now 노드가 갈 수 있는 노드와의 거리를 dist와 함께 더해준다.
- 만약 cost가 distance[now 노드가 갈 수 있는 노드] 보다 작다면?
- distance[now 노드가 갈 수 있는 노드] = cost로 업데이트
- 그리고 heappush(queue, (cost, now 노드가 갈 수 있는 노드))
고찰
- 처음에는 간선에 가중치가 있는 것을 보고 무조건 다익스트라 아니면 플로이드 워셜 둘 중 하나겠거니 했다.
- 거기에 기준 노드를 모르니 모든 노드들 끼리의 최단 거리를 구해야 되기 때문에 플로이드 워셜을 사용하였다.
- 하지만 트리에서는 가중치가 있다고 하더라도 웬만해서는 bfs와 dfs를 사용한다고 한다.
- 트리의 경우에는 두 정점을 잇는 경로가 유일하기 때문에 가중치의 유무에 상관 없이 BFS를 해도 되고, 심지어는 BFS가 아니라 DFS를 해도 된다. 거리가 '갱신되는' 과정 자체가 없기 때문이다.
