STUDY/Algorithm

[백준] 1167 트리의 지름, C++

sinawi95 2022. 10. 12. 18:12
728x90
 

1167번: 트리의 지름

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

www.acmicpc.net

문제 요약

트리의 지름 출력

  • 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것

접근

1. 생각의 흐름

그래프 탐색 두번으로 진행하면 될 것 같다.
아무 점에서 시작해서 가장 먼 지점까지 탐색한다.
첫번째 탐색이 끝나면 가장 먼지점에서 두번째 탐색을 시작한다.

// 1. 아무 노드에서 시작해서 가장 먼노드까지 간 다음,
pair<int,int> tmp;
tmp = bfs({1, 0});
// 2. 가장 먼노드 노드에서 가장 먼노드까지 탐색
tmp = bfs({tmp.first, 0});
cout << tmp.second << endl;

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring> // memset
using namespace std;

#define V_MAX 100001

int V;
vector<vector<pair<int,int>>> G;

void init()
{
    cin >> V;
    for (size_t i = 0; i < V+1; i++)
    {
        G.push_back(vector<pair<int,int>>());
    }
    for (size_t i = 0; i < V; i++)
    {
        int s;
        cin >> s;

        while (1)
        {
            int e, w;
            cin >> e;
            if (e == -1) 
                break;
            cin >> w;
            G[s].push_back({e, w});
        }
    }

}
pair<int,int> bfs(pair<int,int> start) // start = { node, weight = 0}
{
    pair<int,int> ret = {-1, -1};

    queue<pair<int, int>> q;
    q.push(start);

      int visit[V_MAX];
    memset(visit, 0, sizeof(int) * V_MAX);

    while (!q.empty())
    {
        pair<int, int> cur;
        cur = q.front();
        q.pop();

        if (visit[cur.first]) continue;
        visit[cur.first] = 1;

        if (cur.second > ret.second)
        {
            ret.first = cur.first;
            ret.second = cur.second;
        }

        for (auto adj: G[cur.first])
        {
            q.push({adj.first, adj.second + cur.second});
        }
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    init();

    // 그래프 탐색 두번
    // 1. 아무 노드에서 시작해서 가장 먼노드까지 간 다음,
    pair<int,int> tmp;
    tmp = bfs({1, 0});
    // 2. 가장 먼노드 노드에서 가장 먼노드까지 탐색
    tmp = bfs({tmp.first, 0});

    cout << tmp.second << endl;
    return 0;
}
저작자표시