Tree[DFS] - 1967 C++

문제

---

1967번

트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다.

이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다.

정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

 

 

개요

---

앞에서 봤던 다른 문제들과는 다르게 이번에는 간선에 weight(가중치)가 붙어있다.

가중치가 의미하는 것은 그만큼 멀리 떨어져 있다고 생각하면 된다.

가중치가 있으면 인접행렬이 편하므로 인접행렬로 코드를 작성하려 했으나.....

노드의 최대 개수가 10,000 메모리 제한은 128MB이다.

크기가 10,000 * 10,000인 int 타입 2차원 배열의 메모리는 400,000,000Byte 대략 400MB 정도 된다.

크기가 한참 모자르니 어쩔 수 없이 인접리스트를 사용했다.

 

 

 

 

과정

---

트리가 완전 이진 트리가 아닐 수도 있고 각각의 노드에 연결된 가중치가 다르므로 어떻게 가중치를 체크할 지 고민을 많이 했다.

고안한 방법은 C++의 STL인 map을 이용하는 것이다.

map 을 이용하면 내가 원하는 해당 key 값에 value를 저장할 수 있기 때문에 노드의 번호에 따라 가중치를 가져오는 것이 가능해진다.

 

그 다음으로 지름을 구하는 건데.. 여기서 필자는 한 가지 실수를 했다.

처음으로 짠 코드는 그냥 모든 노드를 돌면서 DFS를 실행하고 그 중 가장 긴 길이를 지름이라고 답을 냈다.

이렇게 되면 최악의 경우 10000개의 노드에 대해 재귀함수로 구현한 DFS를 실행하게 되고 당연히 시간은 엄청나게 오래 걸린다.

 

그렇다면 어떻게 해야하느냐.

먼저 루트 노드에서 가장 먼 점을 찾고, 그 점에서 가장 먼 점을 찾으면 그게 트리의 지름이 된다.

DFS를 두 번만 실행해도 문제의 정답을 구할 수 있다.

직관을 위해 가중치는 생략했다.

 

 

 

 

코드

---

#include<iostream>
#include<vector>
#include<map>
using namespace std;

vector<int> graph[10001];
bool visited[10001];
map<int , int> weight[10001];
int sumCourse = 0;
int farNode = 0;
int answer = 0;

void dfs(int a){
    visited[a] = true;
    for(int i = 0; i<graph[a].size(); i++){
        int next = graph[a][i];
        if(visited[next] == true){
            continue;
        }
        sumCourse = sumCourse + weight[a][next];
        dfs(next);
        answer = max(answer, sumCourse);
        if(sumCourse == answer) 
            farNode = next; //한 노드로부터 가장 먼 노드의 번호 저장
        sumCourse = sumCourse - weight[next][a];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    int n, a, b, w;
    cin >> n;
    for(int i = 0; i<n-1; i++){
        cin >> a >> b >> w;
        graph[a].push_back(b);
        graph[b].push_back(a);
        weight[a].insert(pair<int,int>(b,w)); //key에는 다음 노드
        weight[b].insert(pair<int,int>(a,w)); //value에는 가중치
    }
    dfs(1); //루트에서 가장 먼 점 찾기
    for(int i = 0; i<=n; i++){
        visited[i] = false;
    }
    dfs(farNode); //가장 먼 점으로 트리의 지름 구하기
    cout << answer;
    
}