1167 트리의 지름

1167 트리의 지름 (c++)

문제

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

접근 방식

Tree, DFS

1. 트리가 주어짐 (양방향이고 루트가 어딘지 모름)
2. 가장 거리가 먼 두 노드의 거리 (지름)을 구하여 출력
3. 결국 트리의 모든 노드들은 하나 이상의 인접노드와 연결되어 있다. (부모 1, 자식 0 이상)
4. 마지막으로 입력받은 노드부터 DFS를 진행한다.
   1. DFS로 (아직 방문하지 않은) 자식노드를 다 훑음
   2. 자식들 중 가장 긴 노드 2개를 찾고, 둘을 더한 값과 answer를 Max로 비교하여 최신화
   3. 가장 긴 자식을 리턴

문제 풀이

#include <iostream>
#include <vector>
using namespace std;
inline int Max(int a, int b) { return a > b ? a : b; }
int answer = 0;
struct Node
{
    int cost = -1;
    vector<pair<int, int>> adj;
};
vector<Node> v;
int DFS(int root)
{
    v[root].cost = 0;
    int maxTree = 0, subTree = 0;
    for (pair<int,int> iter : v[root].adj)
    {
        if (v[iter.first].cost > -1) continue;
        v[iter.first].cost = DFS(iter.first) + iter.second;
        if (subTree < v[iter.first].cost)
        {
            if (maxTree <= v[iter.first].cost)
            {
                subTree = maxTree;
                maxTree = v[iter.first].cost;
            }
            else subTree = v[iter.first].cost;
        }
    }
    answer = Max(answer, maxTree + subTree);
    return maxTree;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int V, a, b, c;
    cin >> V;
    v = vector<Node>(V + 1, Node());
    while (V-- > 0)
    {
        cin >> a;
        while (true)
        {
            cin >> b;
            if (b == -1) break;
            else cin >> c;
            v[a].adj.push_back({ b, c });
            v[b].adj.push_back({ a, c });
        }
    }
    DFS(v.size() - 1);
    cout << answer << endl;
    return 0;
}

다시 생각해 볼 점

1. 양방향 그래프이기 때문에 if (v[root].cost == -1) continue; 를 해주지 않으면 계속 두 노드를 왔다 갔다 함 (그렇기에 DFS를 시작할 때 v[root].cost = 0 을 해줘야함. (leaf노드까지 고려하여 -1을 방문하지 않은 값으로 채택))
2. DFS 안에서 가장 긴 두 자식인 maxTree 와 subTree 를 구하는 연산이 있는데, 이 때 수행속도와 메모리 효율을 올리기 위해서 둘 다 전역변수로 선언했었다. 하지만 여기서 문제가 발생함

   이 함수는 재귀함수여서 maxTree, subTree는 자식으로 내려가면서 계속 0으로 초기화 됨 (이전값 기억 못함)
   또한, 부모로 올라 올 때, 부모에서 subTree를 건들지 않으면 자식에서 사용한 subTree값이 사용됨 (명백한 설계 오류)

3. 앞으로 실행속도 개선보다도 스코프 기준으로 정확한 변수 범위를 파악하여 사용해야겠다.
   (무조건 전역변수로 설정한다고 이득이 아님)