1967:트리의 지름
1167:트리의 지름 문제에서 아이디어를 얻을 수 있는 문제였다.
트리의 지름 문제를 풀고 본 문제를 풀어서 도움이 되었다.
문제에서 주어진 조건 중에
- 임의의 문제 A에서 B까지 도달하는 경로는 유일하다.
위 조건을 보고 전에 풀었던 트리의 지름 문제가 바로 떠올랐다. 또한,
문제를 풀고 난 후 링크를 통해 한 번 문제를 선택하고 나면, 이전에 풀었던 문제로 다시 돌아갈 수는 없다.
위 조건에 따라 트리의 지름 만큼의 문제를 푸는 것이 최대한 많은 문제를 푸는 조건임을 알 수 있다. 다만 최대한 많은 문제를 풀어야 하기 때문에 동일한 시간이 소요되는 경우의 수가 여러가지 존재하더라도 최대한 많은 노드를 거쳐간 경우의 수를 선택해야 한다.
아래 코드를 보며 이해해보자
from math import ceil
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def dfs(now, cnt):
global dist, endpoint, min_t
if dist < cnt:
dist = cnt
endpoint = now
min_t = visited[now]
elif dist == cnt and visited[now] < min_t:
endpoint = now
min_t = visited[now]
for nxt, time in graph[now]:
if visited[nxt] == -1:
visited[nxt] = visited[now] + time
dfs(nxt, cnt + 1)
N, T = map(int, input().split()) # 문제 수, 하루 풀이 시간 한계
graph = [[] for _ in range(N)]
for _ in range(N - 1):
A, B, C = map(int, input().split())
A -= 1
B -= 1
graph[A].append((B, C))
graph[B].append((A, C))
# 트리의 지름을 이루는 한 정점 구하기
dist, endpoint, min_t = 0, 0, int(1e9)
visited = [-1] * N # 시간 기록
visited[0] = 0
dfs(0, 1)
# 트리의 지름을 이루는 정점으로 답 도출
visited = [-1] * N
dist, min_t = 0, int(1e9)
visited[endpoint] = 0
dfs(endpoint, 1)
print(ceil(min_t / T))우선 방문처리를 할 리스트 visited를 준비한다. 일반적인 DFS에서는 boolean 값으로 방문처리를 하지만 본 문제에서는 visited 함수에 시간(가중치)를 기록하도록 하겠다. 값이 -1이면 최초 방문이다.
-
우선 아무 노드에서나 DFS 함수를 시작해본다. 꼭 0번 노드가 아니라도 상관없다. 어차피 트리 내의 모든 경로는 유일하고, 트리의 지름을 나타내는 경로에 무조건 포함되기 때문이다. (무슨 말인지 이해가 안 된다면 트리의 지름을 풀고 오도록 하자)
-
재귀를 거칠 때마다 visited에 누적 시간(가중치)을 기록한다. 그리고 거쳐간 노드의 개수인 지역 변수 cnt에 1을 더해주고 이것이 전역변수 dist보다 크다면, dist를 cnt로 갱신해준다. 만약 dist == cnt라면 누적된 시간(가중치)가 더 작은지 확인하고, 더 작다면 갱신한다.
-
DFS 함수가 끝나면 endpoint 변수에 DFS 시작 노드에서 가장 먼 노드가 할당되어 있다. 그리고 이 노드는 트리의 지름을 이루는 두 노드 중 하나이다. 트리의 지름을 풀었다면 무슨 말인지 이해가 되어야 한다.
-
트리의 지름을 이루는 두 노드 중 하나를 구했으니 이제 그 노드에서 가장 먼 정점을 구하면 그 두 정점이 이루는 길이가 트리의 지름이다. 이때 함께 도출되는 총 가중치 값(위 코드에서는 min_t 변수에 저장하였다)을 T로 나누고 올림해준 값이 본 문제의 정답이다.
