Tree3 BOJ7812 중앙 트리 7812번 중앙트리 트리와 각 간선의 가중치가 주어질 때 한 꼭짓점에 대해 모든 꼭짓점과의 거리 합이 최소일 때의 그 값을 구한다. 즉 중앙 정점과 모든 꼭짓점과의 거리 합을 구한다. DFS, DP 당연히 모든 점에 대해 거리를 다 계산해볼 순 없고 트리이므로 DFS, 중앙 정점이 될 수 있는 점을 DP로 찾아가며 푼다. 처음에 DFS 두 번에 푸는 방법으로 해결했는데, 한 번만으로도 충분했다. 일단 간선은 벡터 E에 간선을 { 자식 노드 , 가중치 } 로 저장한다. DFS 두 번 하는 방법: 트리 먼저 만들고, 중심을 옮길지 말지 결정 0을 기준으로 모든 정점의 거리 합을 계산한 후 0보다 하위인 정점이 중앙 정점이 될 수 있는지 판단 1. 0에서 DFS, 모든 정점과 0사이의 거리 합 계산 이때 각 .. 2021. 7. 30. BOJ1949 우수 마을 1949번 우수 마을 N개의 마을로 이루어진 트리 형태의 나라에서 우수 마을인 두 마을이 인접하지 않고 우수 마을이 아닌 마을은 적어도 한 우수 마을과 인접해야 할 때 우수 마을로 선정된 마을 주민 수의 최댓값을 구한다. Tree + DP 2535번과 비슷하다. 다만 2535번에서는 v가 선택될 때/아닐 때 두 가지만 고려하면 됐는데 여기서는 v의 자식노드까지 생각해야 한다. 좀 더 상위버전인 듯. 우수마을을 선정하는 조건을 파악하자 1. 우수 마을인 두 마을이 인접하지 않는다. v가 우수마을이면 v의 모든 자식 노드는 우수 마을이 될 수 없다. 2. 우수마을이 아닌 마을은 적어도 한 우수 마을과 인접하다. v가 우수마을이 아니라면 v의 자식 노드 중 하나가 우수 마을이거나, v의 부모 노드가 우수 마을.. 2021. 6. 10. BOJ3716 도로 네트워크 3716번 도로 네트워크 1부터 N까지의 도시를 연결하는 N-1개의 도로가 주어지고 서로 다른 두 도시 D, E가 주어지면 D와 E를 연결하는 도로 중 가장 짧은 것의 길이와 긴 것의 길이를 구한다. 이때 모든 서로 다른 두 도시간 경로는 한 개만 존재한다. ⇒ 주어진 그래프가 트리이다. LCA문제임은 빠르게 파악할 수 있었다. 다만 공통조상뿐 아니라 공통조상까지의 도로의 길이 중 최댓값/최솟값도 알아야 했고 여기저기 헷갈린 탓인지 여러 차례 틀려서 힘들었다ㅠ 1. Get P 먼저 각 도시의 1, 2, 4, 8, ...번째 조상을 조사한다. 1을 root로 하여 BFS로 탐색하고, 조상을 탐색하며 도로 길이의 최소/최대를 구한다. P[ i ][ k ] r = 도시 i의 $2^{\mathrm{k}}$번째 .. 2021. 4. 23. 이전 1 다음
