글 읽기 - 1167번 트리의 지름 문제 질문입니다!

lyradortiz913 3년 전 0

어디가 잘못된 것일까요?

저는 우선 자식이 두개 이상인 아무 노드를 찾아서 그 노드를 기준으로 트리를 축 늘어트린 후 ( 삼각형 형태의 흔한 트리 그림 모양이 되게끔) 가장 멀리 있는 두 점을 찾아서 그 길이의 합을 구하려고 했습니다.

증명을 하기보다는 상당히 직관적으로 접근을 한 것 같고, 코드를 제대로 짰는지도 의문입니다.. 도와주세요...

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 100001;

int V;
vector<bool> visited;
vector<pair<int, int> > tree[MAX];
vector<int> length;

void init(){
    cin >> V;
    visited = vector<bool>(V+1);

    for(int i = 1; i < V + 1; ++i){
        int node;
        cin >> node;
        while(true){
            int adj; cin >> adj;
            if(adj == -1) break;
            int length; cin >> length;

            tree[node].push_back(make_pair(adj, length));   //중복해서 입력되므로 굳이 노드 위치 바꿀 필요 없을 듯.
        }
    }
    /* 트리 확인
    for(int y = 1; y < V+1; ++y){
        for(int x = 0; x < tree[y].size(); ++x){
            cout << tree[y][x].first;
            cout << " : " ;
            cout << tree[y][x].second <<", ";
        }
        cout << endl;
    }*/
}

int getDiameter(){
    sort(length.begin(), length.end(), greater<int>());
    return length[0] + length[1];
}
/*
void dfs(int here, int & len){
    visited[here] = true;
    for(int i = 0; i < tree[here].size(); ++i){
        int there = tree[here][i].first;
        int thereLen = tree[here][i].second;
        if(visited[there] == false){
            len += thereLen;
            dfs(there, len);
        }
    }
}*/

void bfs(int start, int & len){
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while(q.empty() == false){
        int here = q.front(); q.pop();
        int thereLen = 0;
        for(int i = 0; i < tree[here].size(); ++i){
            int there = tree[here][i].first;
            if(visited[there] == false){
                q.push(there);
                visited[there] = true;
                thereLen = max(thereLen, tree[here][i].second );
            }
        }
        len += thereLen;  
    }
}

//자식이 둘 이상인 아무 노드를 하나 루트로 잡아서 bfs?dfs?
//길이 정보 배열에 저장 후 제일 긴 두개 합 == > 지름
void solve(){
    if(V==2){
        cout << tree[0][0].second;
        return;
    }
    int i;
    for(i = 1; i < V + 1; ++i)
        if(tree[i].size()  > 1) break;
    length = vector<int>(tree[i].size(), 0);
    visited[i] = true;
    for(int j = 0; j < tree[i].size(); ++j){
        bfs(tree[i][j].first, length[j]);
        length[j] += tree[i][j].second;
    }    
    int diameter = getDiameter();
    cout<< diameter;
}

int main(void){
    init();
    if(V == 2){
        cout << tree[1][0].second;
        return 0;
    }    
    solve();
    return 0;
}

dohoon 3년 전 1

가장 멀리있는 두 점 중 더 멀리있는 점을 기준으로,

다른 더 먼 점이 존재할 수 있습니다.

dohoon 3년 전 0

좋은 아이디어였고요,

조금 더 발전시키면 답을 얻으실 수 있어요.

제 블로그에다가 정리한 적이 있어요.

lyradortiz913 3년 전 1

@dohoon 이런 반례가 있었네요! 알려주셔서 감사합니다!

블로그글도 잘보겠습니다:)

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

문제

문제

출처

ICPC

1167번 트리의 지름 문제 질문입니다!

lyradortiz913 3년 전 0

dohoon 3년 전 1

dohoon 3년 전 0

lyradortiz913 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말