[백준] 1167번 트리의 지름
in Algorithms on BOJ
Graph(DFS)
문제설명
문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
접근
[백준] 1967번 트리의 지름 문제와 같은 문제이다. 트리의 지름을 구하는 문제인데, 트리의 지름을 찾기 위해서는 어느 한 점에서 DFS를 통해 가장 먼 거리에 있는 점을 찾고 그 점에서 다시 DFS를 이용하면 지름의 양 끝을 지날 수 있고 이를 통해 트리의 지름을 구할 수 있다.
각 노드 별로 연결된 정점 번호가 주어지므로 모두 저장한 후, 위의 설명과 같이 DFS를 두번 수행하면 트리의 지름을 찾을 수 있다.
코드
#include <iostream>
#include <vector>
#define MAX_NUM 100001
using namespace std;
bool visited[MAX_NUM];
vector<pair<int, int> > edges[MAX_NUM];
int d[MAX_NUM];
int dfs(int num){
visited[num] = true;
int ret = num;
for(int i=0; i<edges[num].size(); i++){
int nxt = edges[num][i].first;
int cost = edges[num][i].second;
if(visited[nxt] == false){
d[nxt] = d[num] + cost;
int ret_nxt = dfs(nxt);
if(d[ret] < d[ret_nxt]){
ret = ret_nxt;
}
}
}
return ret;
}
int main(){
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for(int i=0; i<n; i++){
int v, nxt_v, d;
cin >> v >> nxt_v;
while(nxt_v!=-1){
cin >> d;
edges[v].push_back(make_pair(nxt_v, d));
cin >> nxt_v;
}
}
int dv = dfs(1);
fill(visited, visited+MAX_NUM, false);
fill(d, d+MAX_NUM, 0);
int another_dv = dfs(dv);
cout << d[another_dv] << '\n';
}
참고
이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)
