[C++] 백준 온라인 저지 1167번 트리의 지름 풀이

2021.11.18 - [알고리즘 문제 풀이/DFS BFS] - [C++] 백준 온라인 저지 1967번 트리의 지름 풀이

[C++] 백준 온라인 저지 1967번 트리의 지름 풀이

 

 이 문제와 비슷한, 트리의 지름을 구하는 문제

 

---

문제

 

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

출력

첫째 줄에 트리의 지름을 출력한다.

 

 

풀이

 

 1967번과 풀이법은 같은데 입력 스타일만 조금 달라서 입력 받는 부분만 좀 바꿔주고 나머지는 1967번과 같은 풀이로 풀었습니다. 

 입력 자체가 양방향 그래프로 주어지기 때문에 

tree[parent][child] = input;

tree[child][parent] = input; 이런 식으로 하지 않아도 되고 tree[parent][child] = input; 한 줄만 쓰면 됩니다. 

 

 그 다음 DFS 함수를 만들어서 시작 노드부터 가장 깊게 들어가는 노드를 탐색한 뒤 이 노드부터 DFS를 한 번 더 실시합니다. 그러면 반대편으로 가장 깊게 들어가는 노드를 찾게 될 것이고 첫 번째로 찾은 노드와 두 번째로 찾은 노드 사이의 거리가 가장 긴 트리의 지름이 됩니다. 이 두 노드 사이의 거리를 구하면 됩니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int answer = 0; //트리의 지름
int endPoint = 0; //트리의 지름의 한 쪽 정점
void dfs(vector<vector<pair<int, int>>>& tree, vector<bool>& visited, int cur, int weight)
{
    for (int i = 0; tree[cur].size() > i; i++)
    {
        auto next = tree[cur][i].first;
        if (!visited[next])
        {
            visited[next] = true;
            dfs(tree, visited, next, weight + tree[cur][i].second);
        }
    }
    
    //가장 깊은 곳을 찾으면 길이와 정점 정보를 저장한다.
    //첫 번째에 찾은 끝점과 두 번째 찾은 끝점을 연결하면 지름이 된다.
    if (answer < weight)
    {
        answer = weight;
        endPoint = cur;
    }
}

int main()
{
    int V;
    cin >> V;
    
    vector<vector<pair<int, int>>> tree(V + 1); // <정점, 거리>
    for (int i = 0; V > i; i++)
    {
        int parent;
        cin >> parent;
        int child, weight;
        while (true)
        {
            cin >> child;
            if (-1 == child)
                break;
            
            cin >> weight;
            tree[parent].emplace_back(make_pair(child, weight));
        }
    }
    
    vector<bool> visited(V + 1, false);
    visited[1] = true;
    dfs(tree, visited, 1, 0); //첫 번째 정점 탐색
    
    visited.assign(V + 1, false);
    answer = 0;
    visited[endPoint] = true;
    dfs(tree, visited, endPoint, 0); //두 번째 정점 탐색
    
    cout << answer;
    
    return 0;
}