[Python] 1167, 1967 트리의 지름

👉 1167, 1967 트리의 지름

[1967 정답 코드]

from collections import deque


def bfs(graph, visited, distance, d):
    while d:
        start = d.popleft()
        for item in graph[start]: # item[0] == node, item[1] == weight
            if visited[item[0]] == -1:
                visited[item[0]] = 1
                if distance.get(start):
                    distance[item[0]] = distance[start] + item[1]
                else:
                    distance[item[0]] = item[1]
                d.append(item[0])


n = int(input())
graph = {} # parent : [(child, weight), (child, weight)]
visited = [-1] * (n + 1)
distance = {}
d = deque()
# making graph
for i in range(n - 1):
    node1, node2, weight = map(int, input().split())
    if graph.get(node1):
        graph[node1].append((node2, weight))
    else:
        graph[node1] = [(node2, weight)]
    if graph.get(node2):
        graph[node2].append((node1, weight))
    else:
        graph[node2] = [(node1, weight)]

if n == 1: # Error Handling(Runtime Error)
    print(0)
else:
    # first bfs
    visited[1] = 1
    d.append(1)
    bfs(graph, visited, distance, d)
    
    # second bfs
    node = max(distance, key = distance.get)
    visited = [-1] * (n + 1)
    distance = {}
    visited[node] = 1
    d.append(node)
    bfs(graph, visited, distance, d)
    print(max(distance.values()))

[1167 정답 코드]
input 부분만 다름

for i in range(n):
    input_list = list(map(int, input().split()))
    for j in range(1, len(input_list), 2):
        if input_list[j] == -1:
            break
        else:
            if tree.get(input_list[0]) == None:
                tree[input_list[0]] = [(input_list[j], input_list[j + 1])]
            else:
                tree[input_list[0]].append((input_list[j], input_list[j + 1]))

[풀이]
1. 특정 노드(ex. 1)에서부터 가장 먼 거리에 있는 노드를 찾는다. (first BFS)
2. 그 노드로부터 가장 먼 거리에 있는 노드를 찾는다.(Second BFS)
3. 두 노드 사이의 거리 = 트리의 지름

[코드 풀이]
bfs()

• bfs로 탐색을 진행하되, (루트부터) 탐색한 그 노드까지의 거리를 distance 딕셔너리에 (node: distance) 형식으로 저장한다.

node = max(distance, key = distance.get)

• distance 딕셔너리에서 value(distance)가 최댓값인 key(node)를 찾는다.

[오류 해결]

• 처음엔 동적 프로그래밍을 생각하여,(전 문제를 dp로 풀어서 그랬나..) node, edge를 추가할 때마다 트리의 지름을 계속 구해나가는 방법으로 코드를 구현했다. 하지만 바로 시간초과
• 질문 검색을 보면서 위의 풀이에 해당하는 아이디어를 얻었다.

✔ 항상 문제의 본분을 잊지 말자. 처음 트리를 딕셔너리로 구현할 때 루트에서 아래로 내려오면서 parent, child의 관계만 저장하였는데, 위 문제는 트리를 무방향 그래프로 간주한다. 즉, parent, child가 아닌 node와 node의 관계로 생각해 딕셔너리를 짰다면 아이디어를 떠올리는 데 더 수월했을 것이다. (아마 처음 풀이도 그래프로 접근해, DFS or BFS로 짰다면 시간 안에 들어올 수 있지 않았을까..)
✔ BFS 구현 시 queue(deque)을 이용하자

[적용 자료구조 및 알고리즘]

• Graph
• BFS, DFS