BOJ 1167 트리의 지름

LONGNEW·2021년 1월 17일
0

BOJ

목록 보기
65/333

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)

0개의 댓글