[백준 1167] 트리의 지름

문제

문제

 

처음 작성한 코드

import sys

def graph(i):
    far = 0
    diameter = 0
    visited = [False] * (v+1)
    visited[i] = True

    stack = tree[i][:]
    for s in stack:
        visited[s[0]] = True
        if s[1] > diameter:
            far = s[0]
            diameter = s[1]

    while stack:
        node, distance = stack.pop()
        for i in tree[node]:
            if not visited[i[0]]:
                visited[i[0]] = True
                stack.append((i[0], distance + i[1]))
                if diameter < distance +i[1]:
                    far = i[0]
                    diameter = distance+i[1]

    return far, diameter
v = int(sys.stdin.readline())
tree = dict()

for i in range(v):
    tmp = list(map(int, sys.stdin.readline().split()))
    tree[tmp[0]] = list()
    for j in range(1, len(tmp)-1, 2):
        tree[tmp[0]].append((tmp[j],tmp[j+1]))
        
far, _ = graph(1)
print(graph(far)[1])

1. 트리에서 임의의 점을 잡고 거기서 제일 먼 점을 구한다. -> far, _ = graph(1)
2. 그 점과 가장 먼 점을 구하고 그 길이를 출력한다. -> print(graph(far)[1])
3. stack.append할때 i[1]를 넣지않고 distance+i[1]를 추가하는 이유는 i[0]까지의 거리가 distance(그 전 점까지의 거리)와 i[1](그 점부터 i[0]까지의 거리)를 더해줘야하기 때문이다.

 

깨달은 점

• 트리의 지름을 구하는 공식이 있다. 임의의 점에서 제일 먼 점을 구하고 그 점에서 제일 먼 점까지의 거리가 트리의 지름이라고 한다. 처음에 임의의 점 (여기선 1번)에서 제일 먼 점까지의 거리만 출력하게 했는데 예시는 잘 나왔는데 틀렸다고 했다. 보니까 예시가 예외사항을 고려안해도 되는 그런 예시였던 것.... 어쨋든 어렵지만 잘 풀었다!
• 그래프에 관한 문제를 풀때는 stack(dfs), queue(bfs), visited만 생각하면 어떻게 풀 지는 그려질 것 같다.