https://www.acmicpc.net/problem/1167
시간 2초, 메모리 256MB
input :
- V (2≤V≤100,000)
- 간선의 정보 (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)
- 정점 번호 연결된 간선의 정보를 의미하는 정수가 두 개 (정점번호, 정점까지의 거리) 각 줄의 마지막에는 -1이 입력으로 주어진다. (1 <= 거리 <= 10,000)
output :
- 트리의 지름을 출력
조건 :
- 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것
visit이 있는 BFS로 수행해 보자.
BFS(next_node, dis)
다음 노드, 현재까지의 거리를 기록.
"트리의 지름을 구하는 공식은 임의의 하나의 노드 A에서 가장 거리가 먼 노드 B를 구하고,
이 노드 B에서 가장 거리가 먼 노드 C를 구하게 되었을 때,
B와 C 사이의 거리가 트리의 지름이 된다."
ㅋ쿠루삥뽕... 시간 허비의 달인이였던것인가....
리스트에 저장을 해서 찾게 해야 하나 계속 땅만 파다가....
어차피 잘못 만들어 놓은 BFS가 가장 거리가 먼 것을 찾는 것인데, 그냥 노드랑 거리 리턴 시킨 다음에
B에 대해서 BFS 한번 더 돌면 되잖아>? 하는 생각에 하니까 성공했네.....
인제 트리의 지름 공식 이해해 보자...
아래 링크의 타당성 부분을 보고 이해했다...
https://www.weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84#d6
트리 경우에 노드들이 독립적으로 존재하려면 트리가 여러 개 있어야 하는데 그런 경우는 그냥 다른 트리 찾으라는 거 아닌가?
import sys
from _collections import deque
n = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
for i in range(n):
data = list(map(int, sys.stdin.readline().split()))
idx = data[0]
for j in range(1, len(data), 2):
if data[j] != -1:
graph[idx].append((data[j], data[j + 1]))
def bfs(start):
q = deque()
q.append((start, 0))
visit[start] = 1
ret = -9999
while q:
now, dis = q.popleft()
for link in graph[now]:
next_node, next_dis = link[0], link[1]
if not visit[next_node]:
visit[next_node] = 1
q.append((next_node, dis + next_dis))
if dis > ret:
ret = dis
node = now
return ret, node
rad = -9999
visit = [0] * (n + 1)
dis, b = bfs(i)
visit = [0] * (n + 1)
dis, c = bfs(b)
print(dis)
