[골드4] 1967번 : 트리의 지름

🛠 문제

https://www.acmicpc.net/problem/1967

👩🏻‍💻 해결 방법

우선 그래프에 연결된 간선과 가중치를 저장하여 트리를 만들었다
bfs를 통해 최대 가중치를 가지는 인덱스를 먼저 찾아 주고,
해당 인덱스를 시작점으로 bfs를 통해 가중치 합의 최댓값(트리의 지름)을 찾아주었다
(처음엔 bfs를 사용할 것이라고 생각치 못했었다...!)

소스 코드

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

def bfs(start, mode):
  q = deque()
  q.append(start)
  v = [-1 for _ in range(n)]
  v[start] = 0

  while q:
    x = q.popleft()
    for w, nx in graph[x]:
      if v[nx] == -1:
        v[nx] = v[x] + w
        q.append(nx)
  
  if mode == 1:
    return v.index(max(v))
  else:
    return max(v)

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n-1):
  x, y, w = map(int, input().split())
  graph[x-1].append([w, y-1])
  graph[y-1].append([w, x-1])

print(bfs(bfs(0, 1), 2))

💡 다른 사람의 풀이

import sys 
sys.setrecursionlimit(100000) 

def dfs(start, tree, weight, ck): 
  # ck로 루트1번에서 시작한 건지, 최장길이 노드를 루트로 한건지 판단 
  if ck == 1: 
    weight[1] = 0 # 루트 1번 노드 가중치 0으로 설정 
    
    for node, w in tree[start]: 
      if(weight[node] == 0): 
        weight[node] = weight[start] + w # 현재 가중치 + 다음 노드와 가중치 
        dfs(node, tree, weight, ck) 

n = int(sys.stdin.readline()) 
tree = [[] for _ in range(n+1)] 
# 입력 값 tree 생성 
for _ in range(n-1): 
  p_node, c_node, w = map(int, sys.stdin.readline().split()) 
  tree[p_node].append((c_node, w)) 
  tree[c_node].append((p_node, w)) 

weight1 = [0 for _ in range(n+1)] # 루트1로부터 길이를 저장 
dfs(1, tree, weight1, 1) # 루트 1 시작점으로 해 가장 먼 노드를 찾음 

# 찾은 가장 먼 노드를 시작 노드로 탐색 
# 최장경로 노드에서 다시 DFS를 통해 트리지름구하기 
start_node = weight1.index(max(weight1)) 
weight2 = [0 for _ in range(n+1)] 

dfs(start_node, tree, weight2, 2) 

print(max(weight2))