01-26 21:11
Notice
Recent Posts
Recent Comments
Link
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Tags more
Archives
Today
Total
관리 메뉴

너와나의 관심사

백준 1967 트리의 지름 DFS 재귀로 본문

카테고리 없음

백준 1967 트리의 지름 DFS 재귀로

벤치마킹 2019. 5. 6. 21:37


우선 재귀를 어떻게 쓸것인가?


고민이 많이 됩..  결국 믿고 다음 node  로 넘기는것이 답이다 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <iostream> 
#include <algorithm>
#include <memory.h>
 
using namespace std;
int N;
 
typedef struct _arr{
 
    int length;
    int to;
 
 
    struct _arr *next;
    struct _arr *prev;
 
}Arr;
 
Arr *Graph[20001] = { 0, };
Arr temp_buf[2000001] = { 0, };
int NumCnt = -1;
int ans = 0;
int ac[20001] = { 0, };
 
void Init(){
 
    NumCnt = -1;
 
    memset(Graph, 0, sizeof (Graph));
    memset(temp_buf, 0, sizeof (temp_buf));
    memset(ac, 0, sizeof (ac));
 
}
 
 
Arr * getListNode(void)
{
    NumCnt++;
 
    temp_buf[NumCnt].to = 0;
    temp_buf[NumCnt].length = 0;
 
    temp_buf[NumCnt].next = &temp_buf[NumCnt];
    temp_buf[NumCnt].prev = &temp_buf[NumCnt];
 
    return &temp_buf[NumCnt];
}
 
 
Arr * appendListNode(Arr* list, int to , int length)
{
    Arr * node = getListNode();
 
    node->to = to;
    node->length = length;
 
    if (list == NULL)
    {
        return node;
    }
    else
    {
        Arr* last = list->prev;
        last->next = node;
        list->prev = node;
        node->prev = last;
        node->next = list;
 
        return list;
    }
}
 
void Edge(int start, int to, int length){
 
 
    Graph[start] = appendListNode(Graph[start], to, length);
    ac[start]++;
 
}
 
int DFS(int start) {
 
    // max 1 가장큰 반지름 ,  max 2 는 두번쨰 반지름// 
    // 이걸 정의 하는게 힘들다.. //
 
    int max1 = 0, max2 = 0;
    int sum;
    int width = ac[start];
    Arr *temp = Graph[start];
    
    for (int i = 0; i < width; i++){
 
        sum = DFS(temp->to) + temp->length;
 
        if (sum > max1)
        {
            max2 = max1;
            max1 = sum;
        }
        else if (sum > max2){
            max2 = sum;
        }
        else{
            //... .이건 뭐지 ?//
        }
 
        temp = temp->next;
    }
 
    if (ans < max1 + max2) ans = max1 + max2;
    return max1;    
 
}
 
int main() {
 
    int TC = 1;
    int N;
    
    int a, b , l;
 
    freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
    
    cin >>N;
    
    Init();
    
    // 인접리스트 저장
    for (int i = 1; i < N; i++) {
        cin >> a >> b >> l;
        Edge(a, b, l);        
    }
 
    DFS(1);
    cout << ans << "\n";
    return 0;
 
}
cs


저작자표시
Comments