[백준/파이썬]1967번 - 트리의 지름 / bfs, dfs

---

접근 방법

 

1. 잎 노드를 구한다

2. 하나의 잎 노드에서 다른 잎 노드들까지의 길이를 dfs로 계산하여 최대값을 갱신시킨다

---

풀이

 

잎 노드들을 구하는 과정은 루트 노트가 항상 1이므로

1부터 bfs로 더이상 연결된 노드가 없는 노드를 잎 노드로 하여 찾았다.

 

이후 각 잎 노드들에 대해 dfs반복을 하여

다른 잎 노드를 만났을때마다 최대 길이를 비교하여 갱신한다

---

정답 코드

import sys

input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n - 1):
  a, b, v = map(int, input().split())
  graph[a - 1].append((b - 1, v))
  graph[b - 1].append((a - 1, v))

ans = 0

sub = []


def bfs():
  q = [0]
  visited = [0 for _ in range(n)]
  visited[0] = 1
  while q:
    flag = 0
    node = q.pop(0)
    for nextNode, value in graph[node]:
      if visited[nextNode] == 0:
        flag = 1
        visited[nextNode] = 1
        q.append(nextNode)
    if flag == 0:
      sub.append(node)


def dfs(index):
  global ans
  stack = [(index, 0)]
  visited = [0 for _ in range(n)]
  visited[index] = 1
  while stack:
    flag = 0
    node, value = stack.pop()
    for nextNode, nextValue in graph[node]:
      if visited[nextNode] == 0:
        flag = 1
        visited[nextNode] = 1
        stack.append((nextNode, value + nextValue))
    if flag == 0:
      ans = max(ans, value)


bfs()
for i in sub:
  dfs(i)
print(ans)

 

---

오답 풀이

처음에는 단순히 입력값인 a를 부모노드로 생각했는데 꼭 그렇지 않아 잎노드를 잘못 구하는 문제가 있었다

그래서 bfs함수를 추가시켜 잎노드를 따로 구하는 과정을 거쳤다