알고리즘 스터디 - 백준 1967번 : 트리의 지름

문제 해석

1. 두 노드 사이의 거리 중 가장 긴 것을 구하면 된다.
2. 첫째줄에는 노드의 개수가 주어진다. (1 <= n <= 10000)
3. n-1개의 [부모, 자식, 가중치]가 주어짐
4. 루트 노드의 번호는 항상 1
5. 간선의 가중치는 100보다 작은 양수

알고리즘 코드

• 평소와 다르게 일부로 class를 생성해서 문제를 풀었다.
• 이 경우 mode가 있는데 이는 최대 경로를 찾기 위한 노드가 겹치는 경우가 있기에 이를 방지하기 위해서 설정해주었다.

class Graph:

    # vertices는 노드의 수
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj = [[] for _ in range(self.vertices)]
    
    # 연결점과 가중치를 더한 것을 adj라는 곳에 선언
    def addEdge(self, u, v, w):
        self.adj[u].append([v, w])
        self.adj[v].append([u, w])
    
    def BFS(self, u, mode):
        distance = [-1 for _ in range(self.vertices + 1)]

        distance[u] = 0
        queue = deque()
        queue.append(u)

        while queue:

            first = queue.popleft()

            for node, weight in self.adj[first]:
                if distance[node] == -1:
                    distance[node] = distance[first] + weight
                    queue.append(node)
        
        if mode == 1:
            return distance.index(max(distance))
        else:
            return max(distance)

# 노드의 개수 입력
number_of_node = int(input())

G = Graph(number_of_node)

# 노드의 개수 - 1 만큼 [부모, 자식, 가중치] 입력
for _ in range(number_of_node-1):
    parent, child, weight = map(int, input().split())
    G.addEdge(parent-1, child-1, weight)

print(G.BFS(G.BFS(0, 1), 2))