https://www.acmicpc.net/problem/1967
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net
키포인트는 트리 구조의 끝 말단 부분들을 구하는겁니다. 어려운 문제라기보단 아이디어가 필요한 문제고 잘생각하면 정말 쉬운문제인데 어렵게 접근하면 엄청나게 어려울수도 있는 문제네요. 그래도 대략 20분 내로 푼듯하네요 ;; ㅎ
struct Data {
int arrive;
int weight;
};
int n;
vector<vector<Data>>glists;
vector<bool>gbCheck;
vector<int>endPointfinds;
vector<bool>endCheck;
void findendpoint(int k) {
gbCheck[ k ] = true;
bool binit = false;
for (int i = 0 ; i < glists[k].size(); i++) {
if (gbCheck[ glists[k][i].arrive ]==false) {
findendpoint( glists[k][i].arrive );
binit = true;
}
}
if (binit == false) {
endPointfinds.push_back(k);
endCheck.push_back(false);
}
}
int maxs = 0;
void weight(int start,int sum) {
gbCheck[start] = true;
bool binit = false;
for (int i = 0; i < glists[start].size(); i++) {
if (gbCheck[glists[start][i].arrive] == false) {
weight(glists[start][i].arrive, sum+ glists[start][i].weight);
binit = true;
}
}
if (binit == false) {
maxs = max(sum, maxs);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//트리 사이클 없는 무방향 그래프
//트리에서 어떤 두노드를 선태갷도 둘사이에 경로 항상 하나만 존재하게된다
cin >> n;
vector<vector<Data>>lists(n + 1);
vector<bool>bCheck(n+1,false);
for (int i = 0; i < n-1; i++) {
Data tmp;
int start;
int arrive;
int weight;
cin >> start;
cin >> arrive;
cin >> weight;
tmp.arrive = arrive;
tmp.weight = weight;
lists[start].push_back(tmp);
tmp.arrive = start;
lists[arrive].push_back(tmp);
}
glists = lists;
gbCheck =bCheck;
//끝 노드 찾기
findendpoint(1);
//가중치 합
for (int i = 0; i < endPointfinds.size(); i++) {
gbCheck = bCheck;
weight(endPointfinds[i] ,0);
}
cout << maxs;
return 0;
}