[알고리즘] 백준 1167 - 트리의 지름

문제

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

풀이

트리니까 그래프 문제라고 생각했고 각 정점간의 최단거리를 찾는 다익스트라 알고리즘을 활용해서 각 정점에서 가장 먼 지점을 찾고, 그 먼 지점들 중 가장 먼 지점을 찾는 식으로 풀이를 했다. 그치만.. 시간 초과가 나더라 ㅎ

 

시간초과 풀이

from collections import deque
v = int(input())

answer = 0
graph = [[] for _ in range(v+1)]
for _ in range(v):
    arr = list(map(int,input().split()))
    v_num = arr[0]
    new_arr = arr[1:-1]
    for i in range(0,len(new_arr),2):
        graph[v_num].append((new_arr[i],new_arr[i+1]))


def find_max(i):
    global answer
    visited = [0 for _ in range(v+1)]
    q = deque()
    for a in graph[i]:
        q.append(a)

    while q:
        v_,c_ = q.pop()
        if v_ != i and visited[v_] == 0 and c_ > max(visited):
            visited[v_] = c_

            for a in graph[v_]:
                q.append((a[0],a[1]+c_))

    answer = max(answer,max(visited))
        
  
for i in range(1,v+1):
    find_max(i)

print(answer)

 

도저히 시간초과를 해결할 수 없을 것 같아서 풀이를 검색해봤는데 다들 똑같이 하는 말이

1. 임의의 노드에서 가장 먼 노드를 찾는다.

2. 1에서 찾은 노드에서 가장 먼 노드를 찾는다.

3. 그 때의 비용을 출력한다.

 

이렇게 하더라... 쩝 근데 나는 어떻게 임의의 노드에서 시작해서 또 다시 가장 먼 노드를 찾는 저 해답이 어떻게 가장 먼 노드를 찾을 수 있는건지 이해가 안 됐다.... 그러니까 우리는 어떻게 항상 임의의 노드에서 가장 끝인 노드를 찾을 수 있는건지.. 이해가 안 간거다.

 

트리의 지름을 검색해보니 이런 글이 있었다.

https://blogshine.tistory.com/111

[알고리즘] 트리의 지름 : Diameter of Tree

 

설명을 정말 잘 적어두신 것 같다. 역이 모순임을 증명해서 우리가 항상 지름을 구할 수 있는지를 적어두셨는데, 저 일련의 과정은 이해가 갔지만 사실 내가 '트리의 지름'이라는 개념을 모르는 상태에서 이번 1167번 문제같은걸 마주했을 때 내가 스스로 고민하고 생각해서 바로 저 dfs 두번 돌리기 라는 해답을 낼 수 있을지는 모르겠다. ㅠ 음 내가 아직 잘 이해를 못한건지..

 

 

정답 코드

https://fre2-dom.tistory.com/233

[baekjoon] 백준 1167번(파이썬): 트리의 지름

import sys
sys.setrecursionlimit(10 ** 9)


# dfs 탐색
def dfs(x, y):
    # 각 노드와 연결된 노드를 확인
    for a, b in graph[x]:
        # 탐색하지 않은 노드라면
        if visited[a] == -1:
            visited[a] = b + y # 탐색하기까지 걸린 간선의 거리로 초기화
            dfs(a, b + y) # 재귀적으로 탐색


v = int(sys.stdin.readline())

# 각 노드의 연결된 정보를 트리로 표현
graph = [[] for _ in range(v + 1)]
for _ in range(v):
    w = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(w) - 2, 2):
        graph[w[0]].append([w[j], w[j + 1]])


visited = [-1] * (v + 1) # 탐색 여부, 간선의 거리
visited[1] = 0
dfs(1, 0) # 1번 노드에서 dfs 탐색

start = visited.index(max(visited)) # 1번 노드에서 제일 먼 노드를 찾는다.
visited = [-1] * (v + 1)
visited[start] = 0
dfs(start, 0) # 1번 노드부터 가장 먼 노드에서 다시 제일 먼 노드를 찾는다.

# 트리의 지름 출력
print(max(visited))