Study hard
(c++)백준 1967번: 트리의 지름 본문
https://www.acmicpc.net/problem/1967
[풀이]
각 노드를 시작점으로 하여 bfs를 돌려보고 각 노드에서 가장 먼 노드까지의 길이중 가장 긴 것을 출력한다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>//max
#include <cstring>//memset
using namespace std;
struct Pos {
int x, cnt;
};
struct Weight {
int x, weight;//이어진 노드, 간선 가중치
};
int n;
vector<Weight>W[10001];
bool check[10001];
int Max = -1;
void bfs(int start) {
queue<Pos>q;
q.push({ start,0 });
check[start] = true;
while (!q.empty()) {
int x = q.front().x;
int cnt = q.front().cnt;
q.pop();
for (int i = 0; i < W[x].size(); i++) {
int nx = W[x][i].x;
int weight = W[x][i].weight;
if (!check[nx]) {
check[nx] = true;
q.push({ nx,cnt + weight });
Max = max(Max, cnt + weight);
}
}
}
}
void solution() {
cin >> n;
int a, b, w;
for (int i = 0; i < n - 1; i++) {
cin >> a >> b >> w;
W[a].push_back({ b,w });
W[b].push_back({ a,w });
}
for (int i = 1; i <= n; i++) {
memset(check, false, sizeof(check));
bfs(i);
}
cout << Max << endl;
}
int main() {
solution();
return 0;
}
'백준 > bfs, dfs' 카테고리의 다른 글
(c++)백준 9019번: DSLR (0) | 2020.08.29 |
---|---|
(c++)백준 16948번: 데스 나이트 (0) | 2020.08.29 |
(c++)백준 11725번: 트리의 부모 찾기 (0) | 2020.06.22 |
(c++)백준 1991번: 트리 순회 (0) | 2020.06.22 |
(c++)백준 2178번: 미로 탐색 (0) | 2020.06.20 |