트리의 지름은 예전에 풀어봤던 트리의 지름과 또같은 문제이다.
어느 한지점에서 가장 먼지점은 지름에 해당하는 점중 하나이다.
이 생각을 가지고, bfs를 써서 지름에 해당하는 한 지점을 구하고,
구한 지점에서 bfs로 가장 먼지점과의 거리를 구해서 출력해주면 된다.
bfs를 반복해서 쓰는 문제이므로, visited[] 같은 변수를 초기화해주는걸 까먹지 않아야 한다.
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
#define endl "\n"
#define MAX 100000+1
int v;
vector<pair<int,int>> graph[MAX]; // first : 위치, second : 거리
bool visited[MAX];
int length;
int target;
void bfs(int _start){
visited[_start]=true;
queue<pair<int,int>> q;
q.push({_start,0});
while (!q.empty()) {
pair<int,int> w = q.front();
q.pop();
if (length<w.second) {
length=w.second;
target=w.first;
}
for(auto v : graph[w.first]){
if (!visited[v.first]) {
q.push({v.first,w.second+v.second});
visited[v.first]=true;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
//ifstream cin; cin.open("test.txt");
cin>>v;
for (int i=1; i<=v; i++) {
int x,y,z;
cin>>x>>y;
while (y != -1) {
cin>>z;
graph[x].push_back({y,z});
graph[y].push_back({x,z});
cin>>y;
}
}
bfs(1);
// reset();
for (int i=1; i<=v; i++) {
visited[i]=false;
}
length=0;
bfs(target);
cout<<length;
return 0;
}
며칠동안 휴가나와서 안풀었더니 감을 좀 잃은거같다. 문제풀이방법은 알겠는데, 코드를 쓸때 버벅거림이 느껴졌다. 조금만 안풀어도 바로 차이가 온다. 꾸준히 풀자