https://www.acmicpc.net/problem/1167
풀이
트리 내에 임의의 두 점 사이중 가장 거리가 긴 점을 이어야한다.
Root에서 가장 멀리 떨어진 정점으로 풀면 되겠지 했지만.. 안되서 해설을 찾아보았다.
루트에서 가장 멀리 떨어진 점과, 임의의 점에서 부터 가장 멀리 떨어진 정점의 합을 구하면 된다고한다.
저렇게만 보면 쉬운데.. 문제 풀이에 대해 아직 조금 미숙한것 같다.
Code
#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
int V;
queue<int> q;
vector<pair<int, int>> vertax[MAX];
int dis_sum[MAX];
int result, Loc;
void BFS(int idx, int isVisit[MAX])
{
q.push(idx);
while (!q.empty())
{
int now = q.front();
q.pop();
isVisit[now] = 1;
for (int i = 0; i < vertax[now].size(); i++)
{
pair<int, int> temp = vertax[now][i];
int tx = temp.first;
int ty = temp.second;
if (isVisit[tx] != 0)
continue;
if (tx <= 0 || tx > V)
continue;
q.push(tx);
dis_sum[tx] += dis_sum[now] + ty;
if (dis_sum[tx] > result)
{
result = dis_sum[tx];
Loc = tx;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> V;
for (int i = 0; i < V; i++)
{
int node;
cin >> node;
while (1)
{
int ver_node;
cin >> ver_node;
if (ver_node == -1)
break;
int distance;
cin >> distance;
vertax[node].push_back({ ver_node, distance });
}
}
int isVisit[MAX];
fill(isVisit, isVisit + MAX, 0);
BFS(1, isVisit);
result = 0;
fill(dis_sum, dis_sum + MAX, 0);
fill(isVisit, isVisit + MAX, 0);
BFS(Loc, isVisit);
cout << result << "\n";
}
'💻 OnlineJudge > Baekjoon' 카테고리의 다른 글
[백준 / BOJ] C++ 1504 특정한 최단 경로 (0) | 2022.11.10 |
---|---|
[백준 / BOJ] C++ 1238 파티 (0) | 2022.11.10 |
[백준 / BOJ] C++ 1149 RGB거리 (0) | 2022.11.02 |
[백준 / BOJ] C++ 1043 거짓말 (1) | 2022.10.28 |
[백준 / BOJ] C++ 6198 옥상 정원 꾸미기 (0) | 2022.10.19 |