(C++) 백준 1167 트리의 지름

문제 및 풀이

https://www.acmicpc.net/problem/1167
트리

아아아아아 어렵다 1+1를 알려고 정수론을 배울필요 없듯이 ^_^ 그냥 임의의 한 노드에서 가장 먼 노드의 가장 먼 노드가 트리의 지름이다! 라고 받아들이자

dfs 로 위의 로직을 구현하면 답ㄷ이다

코드

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

struct leaf{
    int node; int length;
    leaf(int x, int y): node(x), length(y) {};
};



bool isVisited[100005];

int N; int ans=0;

int farestLeaf=0;
int depth=0;
vector<leaf> leafs[100005];

void solve(int x, int cnt){

    bool flag =false;

    for(int i=0; i< (int) leafs[x].size(); i++){
        int next = leafs[x][i].node;
        if(isVisited[next]) continue;
        isVisited[x]= true;
        solve(next, cnt+leafs[x][i].length);
        flag=true;
    }

    if(!flag){
        if (depth<cnt) {
            depth=cnt;
            farestLeaf = x;
        }
    }
}



int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

     cin>>N;

    //먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.
    int node, length, a;
    for(int i=1; i<=N; i++){
        cin>>a;
        while(1){
            cin>>node; if(node==-1) break;
            cin>>length;
            leafs[a].push_back({node, length});
        }
    }


    solve(1, 0);
    int tmp = farestLeaf;
    memset(isVisited, false, sizeof(isVisited));
    farestLeaf=0;
    depth=0;

    solve(tmp, 0);

    cout<<depth;

}