[백준] 1967 : 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

---

• 루트부터 시작하여 모든 리프노드들까지 dfs 를 통해 검사하며 가장 멀리 떨어진 리프노드를 찾는다.
• 트리 최대 지름의 양 끝점이 될 수 있는 노드들은 루트노드와 리프노드밖에 없다.
• 가중치가 양수이기 때문에 중간에 있는 노드들은 후보에 절대 포함될 수 없다.
• 또한 특정 노드 v 로부터 가장 멀리 떨어진 노드를 찾게 되면, 해당 노드가 양 끝점 중 한 노드가 된다.
• v 를 기준으로 찾은 노드가 다른 양 끝점 중 하나가 아닐 경우, 최대 길이가 될 수 없기 때문이다.
• 한쪽 끝점을 찾았기 때문에, 해당 점에서 dfs 를 돌려 다른 리프노드들을 검사하며 반대쪽 끝점을 찾아 길이를 구하면 된다.

---

#include <iostream>
#include <vector>

using namespace std;

int n, p, c, w;
vector<pair<int,int>> tree[10001];
bool visited[10001];
int target = 0;
int maxLength = 0;

void dfs(int node, int length)
{
    bool exist = false;
    for(int i = 0 ; i < tree[node].size() ; i++)    // 자식노드들 dfs 탐색
    {
        int child = tree[node][i].first;
        if(!visited[child])
        {
            exist = true;
            visited[child] = true;
            dfs(child, length + tree[node][i].second);
        }
    }
    if(!exist)                  // 만약 리프노드 라면
    {
        if(length > maxLength)  // 최대길이인지 확인 후
        {
            maxLength = length; // 길이 갱신
            target = node;      // 다음 시작노드 갱신
        }
    }
}

int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n - 1 ; i++)
    {
        cin >> p >> c >> w;
        tree[p].push_back({c,w});   // 트리를 양방향으로 넣어줌
        tree[c].push_back({p,w});
    }

    visited[1] = true;
    dfs(1, 0);              // 루트부터 시작해서 최대 길이(양 끝점 중 하나)인 노드 찾고
    for(int i = 1 ; i <= n ; i++) visited[i] = false;
    
    visited[target] = true; // 해당 노드부터 다시 최대길이인 노드 찾음
    dfs(target, 0);

    cout << maxLength << endl;
}

---

아래 코드는, 오답인데 아쉬워서 걍 올림

---

• 사실 재귀 한번으로 최대 길이를 구하는 코드를 작성했었다.
• 단방향 트리를 구성하고, dfs 를 통해 루트와 리프들 간의 거리를 통해 최대길이를 확인해준다.
• 노드를 검사하는 과정에서, 자식 노드들은 자기 밑에 있는 구역에서의 가능한 최대 길이를 구해 부모 노드에게 반환한다.
• 백트래킹이랑 비슷한 개념으로 루트-리프, 리프-리프를 모두 검사하는데, 왠지는 모르겠지만 WA 를 받았고, 이유도 모르겠어서 다른 풀이를 참고해서 다시 풀게 되었다.

---

#include <iostream>
#include <vector>

using namespace std;

int n, parent, child, weight;
int answer = 0;
vector<pair<int,int>> tree[10001];

int dfs(int node, int length)   // length 에는 루트(1)부터 해당 node 까지의 거리를 넘겨줌
{
    int sz = tree[node].size();
    if(sz == 1)         // 자식이 하나일 경우
    {                   // 자식노드로 들어가 리프까지 검사하고, 현재구역의 최대길이 반환받아서 부모에게 넘김.
        return dfs(tree[node][0].first, length + tree[node][0].second) + tree[node][0].second;
    }
    if(sz == 2)         // 자식이 양쪽에 다 있을 경우
    {                   // 왼쪽 자식과 오른쪽 자식을 리프까지 훑고, 해당 리프부터 현재 노드까지 거리를 각각 구함
        int left = dfs(tree[node][0].first, length + tree[node][0].second) + tree[node][0].second;
        int right = dfs(tree[node][1].first, length + tree[node][1].second) + tree[node][1].second;
        if(left + right > answer) answer = left + right;    // 이번 노드의 양쪽 최대길이의 합이 최댓값인지 확인
        return (left > right) ? left : right;               // 부모 노드에게 현재구역의 최대길이 반환
    }
    else                // 리프노드일 경우
    {
        if(length > answer) answer = length;    // 루트-리프 의 거리가 최댓값인지 확인
        return 0;
    }
}

int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n - 1 ; i++)
    {
        cin >> parent >> child >> weight;
        tree[parent].push_back({child, weight});        // 트리를 아래 방향으로만 입력받음
    }
    dfs(1, 0);                                          // dfs 를 돌며 최대값을 answer 에 갱신
    cout << answer << endl;                             // 출력
}