028 트리의 지름

첫번째 코드

 

BFS에서 평소에 이용하던 visited만이 아닌 distance를 고려해서 구해야 한다.

그렇기 때문에 tuple로 노드와 가중치를 함께 저장해서 하나씩 풀어가는 형식으로 문제를 풀어야 한다!

책의 도움을...ㅎㅎ; 많이 받았지만 그래도 그만큼 BFS에 익숙해지는 거라고 생각하자!

 

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

n = int(input())
A = [[] for _ in range(n+1)]

for _ in range(n):
    data = list(map(int, input().split()))
    index = 0
    s = data[index]
    index += 1
    while True:
        e = data[index]
        if e == -1:
            break
        v = data[index + 1]
        A[s].append((e, v))
        index += 2
        
distance = [0] * (n+1)
visited = [False] * (n+1)

def BFS(x):
    queue = deque()
    queue.append(x)
    visited[x] = True
    
    while queue:
        now = queue.popleft()
        for i in A[now]:
            if not visited[i[0]]:
                visited[i[0]] = True
                queue.append(i[0])
                distance[i[0]] = distance[now] + i[1]

BFS(1)
Max = 1

for i in range(2, n+1):
    if distance[Max] < distance[i]:
        Max = i

distance = [0] * (n+1)
visited = [False] * (n+1)
BFS(Max)
print(max(distance))

 

통과!

그놈의 DFS, BFS;;

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1167.%E2%80%85%ED%8A%B8%EB%A6%AC%EC%9D%98%E2%80%85%EC%A7%80%EB%A6%84

programmers/백준/Gold/1167. 트리의 지름 at main · ornni/programmers