Study hard
(c++)백준 1967번: 트리의 지름 본문
https://www.acmicpc.net/problem/1967
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 ��
www.acmicpc.net
[풀이]
각 노드를 시작점으로 하여 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 |