트리의 지름

---

문제풀이

트리의 지름은 예전에 풀어봤던 트리의 지름과 또같은 문제이다.

어느 한지점에서 가장 먼지점은 지름에 해당하는 점중 하나이다.

이 생각을 가지고, 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;
}

꾸준히 하자..

며칠동안 휴가나와서 안풀었더니 감을 좀 잃은거같다. 문제풀이방법은 알겠는데, 코드를 쓸때 버벅거림이 느껴졌다. 조금만 안풀어도 바로 차이가 온다. 꾸준히 풀자