[BOJ/C++] 1967: 트리의 지름

🏅 Gold 4

🚨 1차 trouble

다익스트라나 각 노드에 대한 자식 노드의 최대값을 노드에 저장해서 최종적으로 가장 긴 지름값을 갖는 노드를 찾는 방법 시도했으나
자식노드의 노드번호가 부모노드의 노드번호보다 클 경우에 예외처리를 할 방법이 떠오르지 않음
또한 이 방법이 최대지름을 찾는 최적해는 아닌 것 같았음

✏️ 최종 솔루션

1. 부모노드에 자식노드와 가중치 struct 로 push, 자식노드에 부모노드와 가중치 struct 로 push
2. 루트노드에서 가장 먼 정점찾기
   1) 현재 정점에서 갈 수 있는 노드 중에 방문하지 않은 노드만 다음노드로 방문하고 방문할 노드는 방문처리
   ❗️ visited 처리도 양방향으로 해야함 그렇지 않으면 역주행 탐색함
   2) 만약 현재 노드가 리프노드라면 다음에 갈 노드가 없으므로 현재 노드까지의 cnt 값이 최대지름이라면 지름 갱신해주고 노드 번호도 기록
3. 루트노드에서 가장 먼 정점으로부터 가장 먼 정점찾기 ➡️ 최대지름 찾기

📌 self feedback

방향이 없는 트리, 위계가 없는 트리이므로 양방향 그래프인양 접근하는 것이 나음
임의의 정점에서 가장 먼 정점으로부터 가장 먼 정점까지의 거리가 최대지름이 된다는 알고리즘을 알았어야함

🔗 참고 풀이

✏️ 최종 code

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct edge {
    int node;
    int v;
};

vector<vector<edge>> tree;
bool visited[10001][10001];

int leaf;
int dist=-1;
void sol(int cur,int cnt) {
    bool isLeaf=true;
    for(int i=0;i<tree[cur].size();i++) {
        edge e=tree[cur][i];
        int node=e.node;
        int v=e.v;
        
        if(!visited[cur][node]) {
            isLeaf=false;
            visited[cur][node]=true;
            visited[node][cur]=true;
            sol(node,cnt+v);
        }
    }
    
    if(isLeaf && dist<cnt) {
        leaf=cur;
        dist=cnt;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    tree.resize(n+1);
    
    for(int i=1;i<n;i++) {
        int p,c,v;
        cin >> p >> c >> v;
        tree[p].push_back({c,v});
        tree[c].push_back({p,v});
    }
    
    sol(1,0);
    memset(visited,false,sizeof(visited));

    dist=-1;
    sol(leaf,0);

    cout << dist;
}