백준 No.1967 [트리의 지름]

백준 No.1967 [트리의 지름]

---

  문제 

1967번: 트리의 지름 (acmicpc.net)

1967번: 트리의 지름

---

  설명 

 <알고리즘 분류> 
 * DFS

 

  트리의 지름은 트리의 정점들간 경로들 중 가장 긴 거리를 말한다.

 

  DFS를 통해 크게 두 단계로 해결할 수 있다.

1. DFS를 통해 임의의 정점에서 가장 먼 정점을 확인한다.
2. DFS를 통해 위 확인된 정점에서 가장 먼 정점까지의 거리가 트리의 지름이다.

 

저 방법으로 어떻게 트리의 지름이 구해질까?

 

  위 경우는  [A 정점]에서 가장 먼 정점이 [E 정점]으로 잡혔다고 가정할 때 고려할 수 있는 경우의 수를 모두 모은 트리의 모양이다.   [A 정점] 에서 가장 먼 정점은 [E 정점]이므로 [E 정점] 다음으로 또 다른 정점은 있을 수 없다.또한 a, b, c, d, f 는 아래와 같다.

 

  a  ==  [A 정점] --- [B 정점] 사이 가장 먼 거리

  b  ==  [B 정점] --- [E 정점] 사이 가장 먼 거리

  c  ==  [C 정점] --- [A 정점] 사이 가장 먼 거리

  d  ==  [D 정점] --- [B 정점] 사이 가장 먼 거리

  f  ==  [F 정점] --- [B 정점] 사이 가장 먼 거리

 

  A 에서 가장 먼 정점이 E 이므로, 아래 가정이 성립되어야 한다.

• (1) c ≤ a + b
• (2) a + d ≤ a + b && a + f ≤ a + b      → d ≤ b && f ≤ b

  귀류법을 통해 "정점 E가 포함되지 않고 더 긴 트리의 지름이 존재할 수 있다" 라는 명제가 모순된다면 위 방법을 통해 트리의 지름을 구할 수 있다는 사실이 증명된다. 참고로 정점 E 가 포함되지 않았지만 같은 값의 또다른 트리의 지름은 존재할 수 있다! 이 증명은 정점 E 를 포함한 트리의 지름의 길이보다 더 길면서  정점 E를 포함하지 않은 트리의 지름이 존재할 수 있다는 것을 부정하려는 것이다.

 

  [E 정점] 이 포함되지 않으면서 생길 수 있는 트리의 지름은 아래 두 경우이며, 각 경우들이 존재할 수 없는 이유도 아래 적었다.

 

 

Case # 1)

[C 정점] --- c --- [A 정점] --- a --- [B 정점] --- d --- [D 정점]

마지막에 [D 정점] 가 오나 [F 정점] 가 오나 똑같으므로 [D 정점] 만 고려하였다.

위 경우가 성립하려면,
c + a + b ≤ c + a + d,
b ≤ d 가 성립해야 한다.
결국, d ≤ b 이어야 한다는 점에서 b 값과 d 값이 같지 않은이상 Case #1 는 성립할 수 없다.

 

Case # 2)

[F 정점] --- f --- [A 정점] --- d --- [D 정점]

우선, A 에서 가장 먼 정점이 E 라는 점에서

a + f ≤ a + b
-> f ≤ b
-> f  + d ≤ b + d

a + d ≤ a + b
-> d ≤ b
-> d + f ≤ b + f

명제가 성립하여야 한다.
결국, b 의 값이 d 값이나 f 값과 같지 않은이상
위 Case #2 는 성립될 수 없다.

 

  위 두 귀류법을 통해 위 방법으로 트리의 지름을 구할 수 있다는 것이 증명되었다.

 

 <정리> 
1. DFS 를 통해 임의의 정점에서 가장 먼 정점을 확인
2. 위에서 확인된 정점에서 DFS를 한번 더 써서 가장 먼 정점을 확인
3. 2번 과정에서 구해진 두 정점 사이의 거리가 트리의 지름이다.

---

  Code 

#include <iostream>
#include <vector>
#include <cstring>
#define N 10001

using namespace std;

struct s1 {
    int nxt;
    int dist;
};

int n;
int maxVal = 0;
int maxNode = 0;
vector<s1> nodes[N];
bool visit[N];

void dfs(int cur, int val) {
    visit[cur] = true;

    if (maxVal < val) {
        ::maxVal = val;
        ::maxNode = cur;
    }

    for (int i = 0; i < nodes[cur].size(); i++) {
        int nxt = nodes[cur][i].nxt;

        if (!visit[nxt])
            dfs(nxt, val + nodes[cur][i].dist);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    int u, v;
    int dis = 0;

    for (int i = 1; i < ::n; i++) {
        cin >> u >> v >> dis;
        nodes[u].push_back({ v, dis });
        nodes[v].push_back({ u, dis });
    }

    dfs(1, 0);          // 1번 정점에서 가장 먼 정점을 탐색
    memset(visit, false * sizeof(bool), N);
    dfs(::maxNode, 0);    // 탐색한 정점에서 다시 가장 먼 정점 탐색

    cout << ::maxVal;
}