[알고리즘/BFS & DFS] 1967번 : 트리의 지름 - python

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

1967번: 트리의 지름

 

---

• 문제
• 소요시간: 35분 실패

---

• 설계하기(접근방법) 

1. 입력받기

트리의 노드 수와 

간선을 입력받는다

 

2. 구현하기

트리의 가중치, 누적 가중치까지는 잘 구현했다

하지만 그 이후로 어떻게 끝과 끝을 연결해야

트리의 가장 큰 지름을 보장할 수 있을지 몰랐다

 

서치를 해보니 한 노드에서

가장 깊은 곳을 기준으로

다른 깊은 곳을 찾아내면

그것이 트리의 지름을 보장한다고 한다

 

따라서 가장 깊은 노드의 index num을 찾고

또 다시 bfs를 탐색한다

 

 

3. 출력하기

2번째 bfs의 깊이를 출력한다

 

 

---

• 코드(출력)

from collections import deque
import sys

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

    while q:
        temp = q.popleft()
        for child, weight in tree[temp]:
            if visited[child] == -1:
                visited[child] = visited[temp] + weight
                q.append(child)
    m = max(visited)
    return [visited.index(m),m]

input = sys.stdin.readline

n = int(input())

tree = [[]for _ in range(n + 1)]

for _ in range(n - 1):
    p , c , w = map(int, input().split())
    tree[p].append([c,w])
    tree[c].append([p,w])

print(bfs(bfs(1)[0])[1])

---

• 얻어갈 부분

1. 처음 노드의 개수 input을 n으로 받고 그 다음 간선을 또 n으로 받아서  IndexError가 났다. 변수 선언에 주의하자