[알고리즘][Python] 백준 1167 트리의 지름 문제 풀이

문제 출처 : www.acmicpc.net/problem/1167

1167번: 트리의 지름

---

문제 해석 : 트리의 정점과 정점 사이의 거리가 주어 졌을 때 한 정점에서 다른 정점까지의 거리가 가장 멀때의 거리를 구하는 문제이다.

 

문제 풀이 : 이 문제는 BFS, DFS로 풀이 할 수 있다. 이때 아래의 2가지를 주의하면서 차근차근 풀어야 한다.

 

1. 어떤 점에서 출발하는지를 정해야 한다.

-> 항상 1에서 시작하는게 가장 길지 않을 수 있다.

--> 따라서 1번 수행하면서 가장 멀리 있는 정점에서 다시 한번 수행해야한다.

--> ( 어떤 점에서 가장 멀리까지가는 것은 가장 먼 거리의 일부분이기 때문)

 

2. 정점이 1번부터 순서대로 주어지지 않는다.

-> 딕셔너리 생성에 주의해야한다.

---

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

def BFS(i):
    Q = deque()
    Q.append([0,i])

    max_vertex = 0
    max_dist = 0

    visited.add(i)

    while Q:

        now_dist, now_vertex = Q.popleft()

        if now_dist > max_dist:
            max_dist = now_dist
            max_vertex = now_vertex

        for element in graph[now_vertex]:
            next_vertex, next_dist = element

            if next_vertex not in visited:
                Q.append([now_dist+next_dist, next_vertex])
                visited.add(next_vertex)

    return max_dist, max_vertex

V = int(input())
graph = {}

for i in range(V):
    temp = list(map(int, input().split()))[:-1]
    index = temp.pop(0)
    graph[index] = []
    while temp:
        j = temp.pop(0)
        value = temp.pop(0)

        graph[index].append([j,value])

visited = set()
a,b = BFS(1)
visited.clear()
answer, _ = BFS(b)
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.