티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/1967
2. 문제 개요
트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 트리의 지름을 구해서 출력하는 프로그램을 작성하시오.
3. 문제 힌트
루트에서 가장 먼 노드를 찾아가서 거기서 가장 먼 노드를 찾기.
4. 문제 풀이
우선 인접리스트를 만들어야 한다. 그리고 양방향 간선을 연결해주자.
root에서 가장 먼 노드를 BFS로 찾는다. 그리고 그 점을 시작으로 가장 먼 노드를 찾으면 그것이 트리의 지름이 된다.
5. 코드
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
//left, weight
vector<pair<int,int>>adj[10001];
queue<pair<int,int>> q;
bool visited[10001];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n-1; ++i){
int cur, child, weight;
scanf("%d %d %d", &cur, &child, &weight);
adj[cur].push_back(make_pair(child, weight));
adj[child].push_back(make_pair(cur, weight));
}
//루트로 부터 가장 먼 노드 찾기.
fill(visited, visited + 10001, false);
q.push({ 1,0 });
visited[1] = true;
int ansv = -1;
int answ = -1;
while (!q.empty())
{
int cv = q.front().first;
int cw = q.front().second;
q.pop();
if (answ < cw) {
answ = cw;
ansv = cv;
}
int len = adj[cv].size();
for (int i = 0; i < len; ++i)
{
int nv = adj[cv][i].first;
int nw = cw + adj[cv][i].second;
if (!visited[nv])
{
visited[nv] = true;
q.push({ nv,nw });
}
}
}
//루트로부터 가장 먼 노드로 부터 시작해서 가장 먼 노드 찾기
//그냥 BFS한번 더
fill(visited, visited + 10001, false);
q.push({ ansv,0 });
answ = 0;
visited[ansv] = true;
while (!q.empty())
{
int cv = q.front().first;
int cw = q.front().second;
q.pop();
if (answ < cw) {
answ = cw;
ansv = cv;
}
int len = adj[cv].size();
for (int i = 0; i < len; ++i)
{
int nv = adj[cv][i].first;
int nw = cw + adj[cv][i].second;
if (!visited[nv])
{
visited[nv] = true;
q.push({ nv,nw });
}
}
}
printf("%d", answ);
return 0;
}
6. 결과 사진
지적, 댓글 언제나 환영입니다~
'알고리즘 > Tree' 카테고리의 다른 글
백준, boj) 1991. 트리순회 ( C / C++) (0) | 2020.04.14 |
---|
댓글