백준 1967 - 트리의 지름

백준 1967 - 트리의 지름

1차 시도 : 인접 행렬

처음엔 인접 행렬로 구현을 해보았다.
결과는 잘 나오지만, 제출했을 때 메모리 초과가 발생했다.
아무래도 N*N의 2차원 배열을 만들어야 하기 때문에, 충분히 그럴만하다.

#include <iostream>
#include <vector>
using namespace std;
#define MAX 10001

int tree[MAX][MAX]; // 인접 행렬
bool visit[MAX] = { 0, };
int n = 0, max_dist = 0, max_idx;

void clear_vis() {
    max_dist = 0;
    for (int i = 1; i <= n; i++)
        visit[i] = false;
}

void dfs(int start, int dist) {
    visit[start] = true;
    if (max_dist < dist) {
        max_dist = dist;
        max_idx = start;
    }

    for (int i = 1; i <= n; i++) {
        if (!visit[i] && tree[start][i] != 0) {
            dfs(i, dist + tree[start][i]);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        tree[src][dest] = weight;
        tree[dest][src] = weight;
    }
    
    dfs(1, 0);

    clear_vis();
    max_dist = 0;

    dfs(max_idx, 0);

    cout << max_dist;
    return 0;
}

2차 시도 : 인접 리스트

Vector와 Pair를 이용해, 적절히 인접 리스트로 구현했다.
이렇게 하면 양방향 Tree 뿐만 아니라 가중치 또한 저장이 가능하다.
인접 행렬에 비해 자료구조의 크기 또한 매우 작다.

#include <iostream>
#include <vector>
using namespace std;
#define MAX 10001

vector<pair<int, int>> tree[MAX];
bool visit[MAX] = { 0, };
int n = 0, max_dist = 0, max_idx;

void clear_vis() {
    max_dist = 0;
    for (int i = 0; i < MAX; i++)
        visit[i] = false;
}

void dfs(int start, int dist) {
    if (visit[start]) return;

    visit[start] = true;
    if (max_dist < dist) {
        max_dist = dist;
        max_idx = start;
    }

    for (int i = 0; i < tree[start].size(); i++)
        dfs(tree[start][i].first, dist + tree[start][i].second);
}

int main() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        tree[src].push_back(make_pair(dest, weight));
        tree[dest].push_back(make_pair(src, weight));
    }
    
    dfs(1, 0);

    clear_vis();

    dfs(max_idx, 0);
    cout << max_dist;
    return 0;
}