1967번 - 트리의 지름(c++)

🗒 1967번 문제

📌 DFS를 사용해서 구현한 문제 ❗️

1️⃣ 받은 부모 노드, 자식 노드, 가중치를 node vector에 pair로 저장

2️⃣ dfs를 사용해서 root 노드(1)에서 가장 멀리 떨어진 자식 노드를 찾고

3️⃣ 그 다음엔 해당 노드(가장 멀리 떨어진 노드: endpos)에서 멀리 떨어진 노드를 찾기

4️⃣ 가장 멀리 떨어진 노드와의 값이 지름이기에 ans에 넣고 출력

5️⃣ dfs 함수에서는 해당 노드에 들어간 적이 없으면 길이와 endpos값을 재지정해줌

6️⃣ 부모 값에서 dfs함수를 재귀적으로 호출해서 깊이 우선 탐색함 
-> 재귀적으로 호출할 땐 node의 first = child 노드
-> node의 second = length
-> second는 현재 노드의 가중치와 더해서 재귀 dfs로 보내줘야 함❗️❗️
   

➰ 코드로 나타낸 1967번 ➰

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int nodeSize;
int ans = 0, endpos = 0;
vector<pair<int, int>> node[10002];
bool entered[10002];

void dfs(int n, int l) {
	// 이미 들어왔으면 나가
    if(entered[n]) return ;
    
    entered[n] = true;
    // 지름과 끝 노드를 재지정
    if (ans < l){
        ans = l;
        endpos = n;
    }
    
    for (int i = 0; i < node[n].size(); i++) {
    	// 재귀함수 dfs
        dfs(node[n][i].first, l + node[n][i].second);
    }
}

int main() {
    cin >> nodeSize;
    
    int parent, child, length;
    for (int i = 1; i < nodeSize; i++) {
        cin >> parent >> child >> length;
        
        // vector에 넣기
        node[parent].push_back(make_pair(child, length));
        node[child].push_back(make_pair(parent, length));
    }
    
    // root노드부터 먼 값
    dfs(1, 0);
    
    // 다시 받아야 하기에 초기화(ans, entered)
    // memset함수는 첫 인자 배열을 두번째 인자 값으로 모두 초기화해주는데 세번째 인자 크기만큼 해준다.
    ans = 0;
    memset(entered, 0, sizeof(entered));
    
    // 가장 먼 노드에서 먼 값
    dfs(endpos, 0);
    
    cout << ans << endl;
    
    return 0;
}