[백준] 1167번 트리의 지름

💡문제접근

• [[백준] 1967번 트리의 지름] 문제와 동일한 유형의 문제다. 다만 입력값을 받는 방식에서만 차이가 존재한다. DFS or BFS 둘 다 풀이가 가능하지만 BFS로 풀었다.

💡코드(메모리 : 101284KB, 시간 : 1420ms)

from collections import deque
import sys
input = sys.stdin.readline

V = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(V):
	# [정점 번호, 다른 정점 번호, 정점과 정점 사이의 거리] 이후에는 [다른 정점 번호, 정점과 정점 사이의 거리]
    lst = list(map(int, input().strip().split()))
    prev_node = lst[0]
    for i in range(1, len(lst), 2):
        if lst[i] == -1:
            break
        else:
            next_node, cost = lst[i], lst[i+1]
            graph[prev_node].append([next_node, cost])
            graph[next_node].append([prev_node, cost])

def BFS(start, prefix_sum, result):
    queue = deque()
    queue.append([start, prefix_sum])
    while queue:
        s, p = queue.popleft()
        for i in graph[s]:
            node, cost = i
            if result[node] == -1:
                queue.append([node, cost])
                result[node] = result[s] + cost
    return result

result = [-1] * (V+1)
result[1] = 0
BFS(1, 0, result)
num = result.index(max(result))

result = [-1] * (V+1)
result[num] = 0
BFS(num, 0, result)
print(max(result))

💡소요시간 : 17m