vertex cover의 complement가 independent set이라는 걸 이 글을 보고 알았다...


항상 vertex cover 혹은 independent set이라는 단어가 들어가면 기피했었는데, 공부를 미루고 미루다 보니 이 문제에서 화려하게 당했다...


p.s. 어떤 집합을 구하기 어려울 때 여집합을 생각하는 건, 초등학교 시절부터 계속 쓰이는 테크닉일텐데 왜 난 문제를 보면 항상 이런 테크닉이 떠오르지 않는가! 고민해봐야 될 문제인 것 같다

'Algorithm > Problem Solving' 카테고리의 다른 글

Interval graph, Vertex cover, Independent set  (0) 2015.09.30

 



위와 같은 숲(forest)이 있을 때, 0번 정점을 포함하는 트리의 반지름은 6, 지름은 10,

4번 정점을 포함하는 트리는, 반지름이 0, 지름이 0,

1번 정점을 포함하는 트리는, 반지름이 10, 지름이 15입니다.

보너스로 5번 정점의 이심률도 한 번 구해보면 12가 됩니다. 



개념은 이 정도로 하고 실제 구현 쪽으로 넘어가봅시다. 트리의 정점 개수를 n이라고 하면 충격적이게도 지름, 반지름 모두 만에 간단하게 구할 수 있습니다.

또, 좀 생각해보면 반지름보다는 지름이 구하기 훨씬 쉽다는 걸 알 수 있습니다!

따라서 지름을 구하는 방법부터 차근차근 생각해보고자 합니다.



몇 가지 경우를 관찰해 보면 음이 아닌 가중치를 가지는 트리의 지름은 두 단말 노드(leaf node) 사이의 거리일 수밖에 없다는 걸 알 수 있습니다. 이러한 사실은 귀류법으로 쉽게 증명할 수 있습니다. 하지만 여기서는 직관적으로 생각해보도록 하겠습니다.


트리 내부에 있는 임의의 정점을 한 개 잡고 루트라고 합시다. 그리고 두 정점 u와 v를 잡습니다.

일반성을 잃지 않고 v를 내부 정점이라고 생각하면, v의 자식이 존재하고, u와 v 사이의 거리보다 u와 자식 사이의 거리가 더 큰 건 자명합니다.

만약 u와 v 둘 중 어느 것도 내부 정점이 아니라면 이는 우리가 원하는대로 두 정점 모두 단말 노드입니다.

위와 같이 내부 정점이 존재하면 자식으로 내려가면서 거리를 계속 크게 만들 수 있으니 트리의 지름은 단말 노드 사이의 거리 중 한 가지인 건 당연합니다.


여기서 잠깐! 단말 노드가 최악의 경우 개 존재할 수 있고, DFS나 BFS를 각 단말 노드에서 수행하는데 만큼 걸리니 총 시간복잡도는 이겠군요!

모든 노드에서 탐색을 돌리는 것보다 실제 수행시간은 빠르겠지만, 점근적으로 보면 차이가 전혀 없습니다...



슬픔을 딛고 다른 방법을 찾아봅시다. 다음과 같은 방법은 어떨까요?

  1. 아무 정점이나 하나 잡고 탐색을 합니다. 이때 가장 멀리 있는 정점을 u라고 합시다.

  2. u에서 다시 탐색을 해서 가장 멀리 있는 정점 v를 구합니다.

  3. u와 v 사이의 거리가 트리의 지름입니다.

뭔가 될 것 같으면서도 안 될 것 같은 방법입니다. 느낌상 안 될 것 같지만 사실 됩니다! 이 알고리즘의 정당성 증명은 여기에서 보실 수 있습니다. 증명을 대략적으로 읽어 보시면 그냥 경우를 나눠서 귀류법으로 아름답게 노가다해주시면 된다는 걸 알 수 있습니다.


아래는 위 알고리즘을 구현한 소스입니다.


// first: 정점 번호
// second: 간선 가중치
vector<vector<pair<int, int>>> tree;

// v: 현재 노드
// p: 부모 노드
pair<int, int> dfs(int v, int p)
{
    // first: 가중치 합
    // second: 정점 번호
    pair<int, int> ret{0, v};
    for(auto &u: g[v])
    {
        int node = u.first;
        if(node == p) continue;

        auto w = dfs(node, v);
        w.first += u.second;
        ret = max(ret, w);
    }

    return ret;
}

int main()
{
    // ...

    auto v = dfs(0, -1);
    v = dfs(v.second, -1);

    // v.first: 트리의 지름

    return 0;
}


탐색을 두 번 행한 것만으로 지름을 구했으니 총 시간 복잡도는 인 걸 알 수 있습니다.

점근적으로는 우리가 원하는 복잡도를 얻었지만, 탐색을 두 번이나 하니 뭔가 찝찝한 기분이 듭니다. 이 찝찝함을 없애기 위해 이번에는 지름을 구하는 과정을 재귀적으로 생각해봅시다.



어떤 정점 한 개를 뽑고 그 정점을 루트라고 생각합시다. 이때, 이 정점을 포함하는 가장 긴 단순 경로(simple path)는 어떻게 구할까요? 간단합니다. 자식이 한개라면 (그 자식을 루트로 하는 서브트리에서 높이) + (자식으로 가는 간선 가중치)이고, 자식이 두 개 이상이라면 각 자식을 루트로 하는 서브트리의 높이를 모아서 그 중 가장 큰 거 두 개를 뽑아서 조합하면 됩니다. 이것을 재귀적으로 모든 노드에 대해서 반복하면 됩니다!


아래는 이 방법에 대한 구현 코드입니다.


// first: 트리의 지름
// second: 트리의 높이
pair<int, int> dfs(int v, int p)
{
    int d = 0, l = 0;
    int a = 0, b = 0;
    for(auto &u: g[v])
    {
        int node = u.first;
        if(node == p) continue;

        auto w = dfs(node, v);
        d = max(d, w.first);

        int t = w.second + u.second;
        if(a < t) b = a, a = t;
        else if(b < t) b = t;
        l = max(l, t);
    }

    return {max(d, a + b), l};
}


이제 트리의 반지름에 대해서 생각해봅시다. 몇 가지 경우를 살펴보다 보면 트리의 반지름을 결정해주는 정점은 항상 지름을 결정하는 두 정점의 경로 위에 있다는 걸 알 수 있습니다. 이는 귀류법을 이용한 증명(이라고 쓰고 노가다라고 읽는다.) 과정을 통해 보일 수 있습니다. 


그런데 여기서 잠시 멈추고 이런 생각을 해봅시다.

트리의 지름을 결정하는 정점들이 여러 쌍 존재할 수도 있는데, 한 개의 경로만 확인해서 제대로 반지름을 구할 수 있을까?

만약 이게 성립하지 않으면 반지름을 구하는 작업은 무척 지루하고 고통스러운 작업이 되겠지만, 다행히도 저 질문의 답은 "예"입니다. 이는 트리의 지름을 결정하는 여러 경로들은 반드시 반지름을 결정하는 정점을 교점으로 지난다는 특성 때문입니다. 이러한 특성도 귀류법으로 쉽게(?) 증명할 수 있습니다.



트리의 지름, 반지름을 적절히 이용하는 문제로 IOI 2013 1번(링크)이 우리를 기다리고 있습니다.

참고로 이심률, 반지름, 지름은 임의의 그래프에서도 트리와 같은 방법으로 정의할 수 있습니다.

'Algorithm > Study' 카테고리의 다른 글

트리의 지름, 반지름, 이심률(?)  (6) 2015.02.27
  1. 사포 2015.02.21 20:09 신고

    좋은 글이군요. 감사합니다.

  2. ksh 2015.02.21 22:08 신고

    알고리즘합시다!

  3. 2015.03.04 20:34

    비밀댓글입니다

    • 스스. 2015.03.05 10:54 신고

      앗 다른 분 소스랑 착각했나 보네요 ㅜㅜ
      책장문제는 꼭 풀어보세요 진짜 무슨 약을 하면 이런 문제를 낼 수 있는지 의문이 드는 문제에요 하하...

  4. 2015.03.25 18:41

    비밀댓글입니다

  5. TPS 2015.07.06 15:34 신고

    트리 나오는 순간 껐다.
    -조인철

+ Recent posts