n개의 꼭짓점으로 구성된 무향 나무가 있고 꼭짓점에 사과가 몇 개 있는 0에서 n-1까지 번호가 매겨져 있다고 가정합니다. 우리는 나무의 한쪽 가장자리를 걷는 데 1초를 보냅니다. 정점 0에서 시작하여 이 정점으로 되돌아오는 트리의 모든 사과를 수집하기 위해 소비해야 하는 최소 시간(초)을 찾아야 합니다.
여기에서 무방향 트리의 에지는 배열 에지에 주어집니다. 여기서 edge[i] =[from_i, to_i] 이것은 정점 from_i와 to_i를 연결하는 에지가 존재함을 의미합니다. 또한, 사과가 있는 또 다른 배열이 있습니다. 여기서 hasApple[i] =true는 정점 i에 사과가 있음을 의미하고, 그렇지 않으면 사과가 없습니다.
따라서 입력이 n =7이고 edge =[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]인 경우 , 그리고 사과 =[거짓, 거짓, 참, 거짓, 참, 참, 거짓]이 있으면 출력은 8이 됩니다.
위의 이미지에서 빨간색 정점에 사과가 있는 나무를 볼 수 있습니다. 모든 사과를 모으는 최적의 경로는 녹색 화살표로 표시됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
방문한 한 세트 정의
-
dfs() 함수를 정의하면 노드, par, 배열 a, 배열 그래프[],
가 사용됩니다. -
온도 :=0
-
그래프[노드]의 각 요소 x에 대해 -
-
x가 par와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
임시 :=임시 + dfs(x, 노드, a, 그래프)
-
-
ret :=ret + temp * 2
-
a[node] + temp> 0이면 true를 반환하고, 그렇지 않으면 0
을 반환합니다. -
주요 방법에서 다음을 수행하십시오 -
-
ret :=0
-
그래프라고 하는 n개 목록의 배열을 정의합니다.
-
initialize i :=0의 경우 i
-
그래프 끝에 e[i, 1] 삽입[e[i, 0]]
-
그래프 끝에 e[i, 0] 삽입[e[i, 1]]
-
-
dfs(0, -1, a, 그래프)
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
class Solution {
public:
set<int> visited;
int ret;
int dfs(int node, int par, vector<bool>& a, vector<int> graph[]){
int temp = 0;
for (int x : graph[node]) {
if (x == par)
continue;
temp += dfs(x, node, a, graph);
}
ret += temp * 2;
return a[node] + temp > 0;
}
int minTime(int n, vector<vector<int> >& e, vector<bool>& a){
ret = 0;
vector<int> graph[n];
for (int i = 0; i < e.size(); i++) {
graph[e[i][0]].push_back(e[i][1]);
graph[e[i][1]].push_back(e[i][0]);
}
dfs(0, -1, a, graph);
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
vector<bool> v1 = {false,false,true,false,true,true,false};
cout << (ob.minTime(7,v, v1));
} 입력
7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}},
{false,false,true,false,true,true,false} 출력
8