[백준/BOJ] 1167: 트리의 지름 구하기

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

 

---

 

 

문제

---

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

입력

---

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

출력

---

첫째 줄에 트리의 지름을 출력한다.

 

예제 입력

---

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

 

예제 출력

---

11

 

코드 

---

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 100001

vector<pair<int, int>> tree[MAX];
bool visited[MAX];
int len, max_v;

void dfs(int v, int l) {
	visited[v] = true;
	if (len < l) {
		len = l;
		max_v = v;
	}
	
	for (size_t i = 0; i < tree[v].size(); i++) {
		int next = tree[v][i].first;
		int dist = tree[v][i].second;
		if (!visited[next]) {
			dfs(next, l + dist);
		}
	}
}

int main() {
	int v;
	cin >> v;
	for (int i = 0; i < v; i++) {
		int a, b, c;
		cin >> a;
		while(true) {
			cin >> b;
			if (b == -1) break;
			cin >> c;
			tree[a].emplace_back(make_pair(b, c));
		};
	}

	dfs(1, 0);
	memset(visited, 0, sizeof(visited));
	dfs(max_v, 0);

	cout << len;
	return 0;
}

 

 

 

---

 

 

시간 초과로 고생한 문제.

모든 정점을 기준으로 탐색을 해서 시간초과가 뜨는 것 같아서 연결된 간선이 1개인 정점에서만 탐색을 하도록 코드를 수정했지만, 이 방법도 시간 초과가 떴다.

해결을 못해서 검색을 해본 후 2개의 정점만 탐색하고 답을 구할 수 있다는 것을 알게됐다(밑에 reference 참고).

특정 정점 a를 정하고, 그 정점에서 가장 먼 정점 b을 찾는다. 다음으로 정점 b에서 가장 먼 정점 c를 찾는다. 트리의 지름은 정점 b와 정점 c 사이의 거리이다.

특정 정점에서 가장 먼 정점을 찾기위해 dfs를 실행해주면 되고 총 2번의 dfs를 실행하여 문제를 해결할 수 있다.

 

reference

https://blog.myungwoo.kr/112