그래프 (1) 썸네일형 리스트형 2021년 정올 본선 2번 그래프 균형 맞추기 루트의 가중치를 미리 0으로 정해둔다고 생각해보자. 그러면 루트와 이어진 정점들은 간선과 같은 가중치를 가지게 되고 그와 이어진 정점들도 간선 가중치 - 이전 정점 가중치가 부여되게 된다. 따라서 모든 정점들은 루트에 의해 가중치가 고정되고 이는 dfs 한번에 구할 수 있다.좀더 자세히 살펴보면 루트로부터의 거리가 홀수면 루트의 가중치가 늘어남에 따라 같이 늘어나고 짝수면 반대로 줄어들게 된다.절댓값의 합을 구하기 때문에 루트의 값이 너무 커지거나 작아지면 최솟값을 구할 수 없고 따라서 그 사이를 삼분탐색으로 구할수 있을 거라는 생각을 했다. 처음에는 트리로 문제를 잘못봐서 삼분탐색만 생각했는데 사이클이 있을 수 있었다.앞서말한 거리에 따라 정점들을 증가와 감소로 경우를 나누어 생각하면 처음 dfs를 돌.. 이전 1 다음