[알고리즘] Day3 - 1967번 트리의 지름

00 문제

01 트리의 지름?

• 트리는 사이클이 없는 무방향 그래프이며, 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재한다.
• 트리에서 어떤 두 노드를 선택해서 양쪽으로 당기면, 가장 길게 늘어나는 경우가 있다.
• 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝점으로 하는 원 안에 들어가게 된다.
• 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 
• 정확히는 트리에 존재하는 모든 경로들 중 가장 긴 경로의 길이를 말한다.
• 가장 먼 두 정점 사이의 거리 or 가장 먼 두 정점을 연결하는 경로를 의미한다.

02 트리의 지름을 구하는 방법

• 트리에서 임의의 정점 x를 잡는다.
• 정점 x에서 가장 깊은 노드 중 가중치가 가장 큰 정점 y를 찾는다. -> DFS 이용
• 정점 y에서 가장 깊은 노드 중 가중치가 가장 큰 정점 z를 찾는다. -> DFS 이용
• 트리의 지름은 정점 y와 정점 z를 연결하는 경로다. (y-z)

03 DFS를 두번 이용하여 트리의 지름을 구한다.

• 가중치가 가장 큰 정점을 찾기 위해서 push 할 때 마다 sPos, sMax에 현재 노드와 거리 값을 저장한다.
• 연산이 전부 끝난 후 sMax 배열 중 가장 큰 값을 찾아 sMax_에 저장한 후, 같은 인덱스에 해당하는 sPos를 가장 먼 지점이라고 생각한다.

void depth_first_search(int N, int V)

{

        int i = 0, j = 0, distance = 0;

        int row = V;

        push(V);

        while (is_empty())

        {

               visited[row] = 1;

               if (adj_mat[row*(N + 1) + i] && !visited[i])

               {

                       push(i);

                       sPos[j] = i;

                       distance += adj_mat[row*(N + 1) + i];

                       sMax[j++] = distance;

                       row = i;

                       i = 0;

               }

               if (i == N)

               {

                       pop();

                       distance -= adj_mat[row*(N + 1) + top()];

                       row = top();

                       i = 0;

               }

               i++;

        }

}

void find_diameter(int N)

{

        int i, sPos_, sMax_ = 0;

        depth_first_search(N, 1);

        for (i = 0; i < N+1; i++)

        {

               visited[i] = 0;

               if (sMax[i] > sMax_)

               {

                       sMax_ = sMax[i];

                       sPos_ = sPos[i];

               }

        }

        depth_first_search(N, sPos_);

        for (i = 0; i < N + 1; i++)

        {

               if (sMax[i] > sMax_)

               {

                       sMax_ = sMax[i];

                       sPos_ = sPos[i];

               }

        }

        printf("%d", sMax_);

}

04 전체 코드

// Day3 2018.08.02

// 1967번 : 트리의 지름 (The diameter of the tree)

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#define scanf scanf_s

typedef struct _dnode {

        int key;

        struct _dnode *prev;

        struct _dnode *next;

}dnode;

dnode *head, *tail;

void init_node();

int push(int k);

int pop();

void clear_node();

int is_empty();

int top();

char *adj_mat;

bool *visited;

int *sMax, *sPos;

void adjacent_matrix(int V);

void print_matrix(int N);

void depth_first_search(int N, int V);

void find_diameter(int V);

int main()

{

        int N;

        scanf("%d", &N); // 노드의 개수 1 ~ 10,000

        adj_mat = (char *)calloc((N + 1)*(N + 1), sizeof(char));

        visited = (bool *)calloc(N + 1, sizeof(bool));

        sMax = (int *)calloc(N + 1, sizeof(int));

        sPos = (int *)calloc(N + 1, sizeof(int));

        init_node();

        adjacent_matrix(N);

        //print_matrix(N);

        //printf("- - - - - - - \n");

        find_diameter(N);

        // finish

        free(visited);

        free(adj_mat);

        clear_node();

        return 0;

}

void adjacent_matrix(int N)

{

        int i, parent, child, weight;

        for (i = 0; i < N - 1; i++)

        {

               scanf("%d %d %d", &parent, &child, &weight);

               adj_mat[parent*(N + 1) + child] = weight;

               adj_mat[child*(N + 1) + parent] = weight;

        }

}

void print_matrix(int N)

{

        int i, j;

        // print

        for (i = 0; i < N + 1; i++)

        {

               printf("row %3d > ", i);

               for (j = 0; j < N + 1; j++)

               {

                       printf("%3d ", adj_mat[i*(N + 1) + j]);

               }

               printf("\n");

        }

}

void depth_first_search(int N, int V)

{

        int i = 0, j = 0, distance = 0;

        int row = V;

        push(V);

        //printf("> push %d\n", push(V));

        while (is_empty())

        {

               visited[row] = 1;

               if (adj_mat[row*(N + 1) + i] && !visited[i])

               {

                       push(i);

                       //printf("> push %d now %d next %d weight %d ", push(i), row, i, adj_mat[row*(N+1)+i]);

                       sPos[j] = i;

                       distance += adj_mat[row*(N + 1) + i];

                       //printf("-> distance %d\n", distance);

                       sMax[j++] = distance;

                       row = i;

                       i = 0;

               }

               if (i == N)

               {

                       pop();

                       //printf("> pop %d ", pop());

                       //printf(" now %d prev %d weight %d ", row, top(), adj_mat[row*(N+1)+top()]);

                       distance -= adj_mat[row*(N + 1) + top()];

                       //printf("-> distance %d\n", distance);

                       row = top();

                       i = 0;

               }

               i++;

        }

}

void find_diameter(int N)

{

        int i, sPos_, sMax_ = 0;

        depth_first_search(N, 1);

        for (i = 0; i < N+1; i++)

        {

               visited[i] = 0;

               //printf("sMax %d sPos %d\n", sMax[i], sPos[i]);

               if (sMax[i] > sMax_)

               {

                       sMax_ = sMax[i];

                       sPos_ = sPos[i];

               }

        }

        //printf("sMAX_ %d sPos_ %d\n", sMax_, sPos_);

        depth_first_search(N, sPos_);

        for (i = 0; i < N + 1; i++)

        {

               if (sMax[i] > sMax_)

               {

                       sMax_ = sMax[i];

                       sPos_ = sPos[i];

               }

        }

        printf("%d", sMax_);

        //printf("sMAX_ %d sPos_ %d\n", sMax_, sPos_);

}

void init_node()

{

        head = (dnode *)calloc(1, sizeof(dnode));

        tail = (dnode *)calloc(1, sizeof(dnode));

        head->prev = head;

        head->next = tail;

        tail->prev = head;

        tail->next = tail;

}

/* * * * * * * * * * * * *

**      Stack push and pop * *

** * * * * * * * * * * * */

int push(int k)

{

        dnode *t;

        if ((t = (dnode *)malloc(sizeof(dnode))) == NULL)

        {

               printf("Out of memory !\n");

               return -1;

        }

        t->key = k;

        head->next->prev = t;

        t->next = head->next;

        t->prev = head;

        head->next = t;

        return k;

}

int pop()

{

        dnode *t;

        int k;

        if (head->next == tail)

        {

               printf("Stack underflow !\n");

               return -1;

        }

        t = head->next;

        k = t->key;

        head->next = t->next;

        t->next->prev = head;

        free(t);

        return k;

}

void clear_node()

{

        dnode *t, *s;

        t = head->next;

        while (t != tail)

        {

               s = t;

               t = t->next;

               free(s);

        }

        head->next = tail;

        tail->prev = head;

}

int is_empty()

{

        if (head->next == tail)

        {

               //printf("Linked list is empty !\n");

               return 0;

        }

        return 1;

}

int top()

{

        dnode *t;

        t = head->next;

        if (t == tail)

               return -1;

        return t->key;

}

99 참고 자료

• [백준 알고리즘 1967번 : 트리의 지름] https://www.acmicpc.net/problem/1967
• [트리의 지름 구하는 법의 증명] http://blog.myungwoo.kr/112