[python3] 1167 풀이 (트리의 지름, 트리, DFS)

문제가 어려워서 힌트를 봤고 이해하고 나니 쉽게 풀 수 있었다.

트리가 주어진다. 이때 트리의 지름을 구하는 문제이다. 트리의 지름을 어떻게 구해야하는지 이해하지 못하면 풀수가 없다.

트리가 주어졌을대 트리의 지름을 구하기 위해서는 가장 끝점을 알아내야한다.
처음에는 각 노드마다 다익스트라를 할지 플로이드를 할지 고민했다. 그런데 주어지는 노드가 100,000개이기 때문에 구할 수가 없다. 따라서 다른 방법을 사용해야한다. 
그래서 이리저리 지지고 볶으니 한줄로 세우는 방법이면 되지 않을까 싶었다. 그래서 한줄로 세워보았다.

그런데 이렇게 세운다고 달라지지가 않았다. 더이상 고민하는게 무의미하여 찾아보니 아무 노드나 잡고 가장 먼것을 찾아본다. 그럼 지름의 끝 노드를 찾을 수 있었다. 만약 3번 노드에서 시작하는 경우 DFS로 5번이 가장 멀다는 것을 확인가능하다.

그런데 이때 백트래킹을 사용할수가 없어서 DFS로 모든 노드를 방문하며 각 노드별 값을 찾아준다.

그러면 5번 노드의 위치가 가장 긴것을 확인가능하다. 이제는 5번 노드를 시작으로 각 노드별 거리를 구해본다.

그럼 최종적으로 1번 위치에서 가장 높은 값을 가지므로 이 트리의 지름은 11이라고 판단할 수 있다. 원리는 쉬우나 이걸 떠올리기가 어려웠다. 이를 코드로 작성하면 아래와 같다.

N = int(input())
visited = {}
adj = {}
for i in range(N):
    tmp = list(map(int, input().split()))
    nodeNum = tmp[0]
    visited[nodeNum] = False
    i = 1
    while True:
        if tmp[i] == -1:
            break
        nextNode = tmp[i]
        i += 1
        weight = tmp[i]
        i += 1
        if nodeNum in adj:
            adj[nodeNum].append([nextNode, weight])
        else:
            adj[nodeNum] = [[nextNode, weight]]
final = [0, 0]


def DFS(node, total):
    global final
    if final[1] < total:
        final = [node, total]
    # weight가 가장 큰거 뽑기
    for nextItem in adj[node]:
        nextNode, weight = nextItem
        if visited[nextNode] != True:
            visited[nextNode] = True
            DFS(nextNode, total+weight)


visited[nodeNum] = True
DFS(nodeNum, 0)
node, weight = final
final = [0, 0]
for key in visited:
    visited[key] = False
visited[node] = True
DFS(node, 0)
print(final[1])