글 읽기 - 트리의 지름 문제인데 85%에서 틀렸다네요 ㅜ

korocg 3년 전 0

입력을 graph로 일단 만들고 나서 최장경로가 될 수 있는 후보인 잎-잎 , 루트-잎 간의 거리에 대한 최댓값을 재귀함수로 구했는데

어디가 틀렸는지 모르겠어요 ㅠ

이 방법말고 루트에서 제일 먼 점에서 가장 먼 점 구하는 방법으로는 맞았는데 이렇게 하면 틀리네요 왜 이럴까요??

#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define pb push_back
#define endl '\n'
#define MAX 0x7FFFFFFF
#define MIN 0x80000000
using namespace std;

int N;
vector<tuple<int,int,int>> edge;
vector<vector<pair<int,int>>> graph;
int longest=MIN;
int getDistance(int idx){
    vector<int> dist;
    for(int i=0; i<graph[idx].size(); i++){
        dist.pb(graph[idx][i].second + getDistance(graph[idx][i].first));
    }

    if(dist.empty()) {
        return 0;
    }
    if(dist.size()==1){
        longest = max(longest, dist[0]);
        return dist[0];
    }
    
    sort(dist.begin(), dist.end());
    int len = dist.size();
    longest = max(longest, dist[len-1]+dist[len-2]);
    return dist[len-1];
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt","r",stdin);

    cin >> N;
    graph.assign(N+1, vector<pair<int,int>>());
    for(int i=0; i<N; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].pb({b,c});
    }

    int result = getDistance(1);

    cout << max(result,longest);

    return 0;
}

korocg 3년 전 0

아 입력이 N개가 아니라 N-1개네요 트리가 될수있는 조건인데 이거를....ㅠ 고쳤습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

트리의 지름 문제인데 85%에서 틀렸다네요 ㅜ

korocg 3년 전 0

korocg 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말