[백준/파이썬] 1967번 트리의 지름

https://www.acmicpc.net/problem/1967\

1967번: 트리의 지름

 

---

문제 & 테스트 케이스

---

문제 해석

노드에서 노드까지 가장 먼 거리를 찾는 문제.

---

코드

1. 제출

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

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))
    adj[b].append((a, c))

def find(start_node):
    score = 0
    visit = [0] * (n + 1)
    visit[start_node] = 1
    q = deque()
    q.append((start_node, 0))
    while q:
        current_node, dist = q.popleft()
        score = max(score, dist)
        for next_node, next_cost in adj[current_node]:
            if visit[next_node]: continue
            q.append((next_node, dist + next_cost))
            visit[next_node] = 1
    return score

ans = 0
for i in range(1, n + 1):
    # 리프 노드인 경우 탐색
    if len(adj[i]) == 1:
        ans = max(ans, find(i))
print(ans)

2. 제출

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

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))
    adj[b].append((a, c))

def find(start_node):
    score = 0
    visit = [0] * (n + 1)
    visit[start_node] = 1
    q = deque()
    q.append((start_node, 0))
    power_node = 0
    while q:
        current_node, dist = q.popleft()
        if dist > score:
            score = max(score, dist)
            power_node = current_node
        for next_node, next_cost in adj[current_node]:
            if visit[next_node]: continue
            q.append((next_node, dist + next_cost))
            visit[next_node] = 1
    return score, power_node

a, start_node = find(1)
ans, a = find(start_node)
print(ans)

---

문제 풀이

1번 코드 풀이

처음 생각한 방식은 트리가 주어졌을 때 가장 먼 거리가 나타날 조건은 리프 노드에서 출발하여, 리프 노드에 도달 할 경우라고 생각했다.

따라서 간선의 수가 한개인 노드(리프 노드)에서 모두 dfs를 통해 가장 먼 거리를 갱신해가며 답을 구해주었다. -> Solve

 

시간 초과가 나지 않았지만 최적화된 풀이가 아니였다.

문제에서 노드가 주어진다.

따라서 노드에서 dfs 탐색을 통해 가장 먼 리프 노드를 구할 수 있다.

이 노드는 트리의 지름의 한 점이 될 수 밖에 없다. 따라서 이 점에서부터 다시 dfs 탐색을 하여 가장 긴 거리

즉, 트리의 지름을 구할 수 있다.

겨우 두번의 dfs 탐색을 하기 때문에 최적화된 방식으로 문제를 해결 할 수 있다.