[백준] 1967 - 트리의 지름

이 문제는 BFS에 넣어두긴 했지만 트리 구조를 인접행렬로 만드는게 더 중요한 문제

1. 입력되는 간선의 정보와 가중치를 map과 w배열을 만들어 저장

2. 트리의 마지막 노드에서 출발하는 것이 가장 큰 값을 나타내게 되기 때문에 map에서 갈 수 있는 정점의 수가 1개인 곳만 찾아서 bfs 탐색

결과적으로는 맞았지만 1832ms나 걸렸기 때문에 효율적이라고는 생각되지 않는코드

#include <iostream>
#define MX 10002
using namespace std;
 
int map[MX][1000], w[MX][1000], q[MX];
int N, dab;
 
void bfs(int snode)
{
    int check[MX] = { 0 };
    int st, ed, inode, nnode, tmp = 0;
    st = ed = -1;
    q[++st] = snode; check[snode] = 1;
    while (st != ed)
    {
        inode = q[++ed];
        if (check[inode] > tmp) tmp = check[inode];
        for (int i = 1; i<=map[inode][0]; i++)
        {
            nnode = map[inode][i];
            if (nnode == 0 || check[nnode]) continue;
            q[++st] = nnode; check[nnode] = check[inode] + w[inode][i];
        }
    }
    if (tmp > dab) dab = tmp;
}
 
int main(void)
{
    cin >> N;
 
    for (int i = 1; i < N; i++)
    {
        int p, s, c;
        cin >> p >> s >> c;
        map[p][0]++; map[p][map[p][0]] = s; w[p][map[p][0]] = c;
        map[s][0]++; map[s][1] = p; w[s][1] = c;
    }
 
    for (int i = 1; i <= N; i++)
        if (map[i][0] == 1) bfs(i);
    cout << dab - 1 << endl;
    return 0;
}