[백준] 1167번 트리의 지름

문제 출처: https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

1967의 트리의 지름과 동일한 문제라고 생각해서 입력부분의 처리만 변경하여 동일한 알고리즘을 돌렸지만 시간초과가 발생했다.

1967번 문제는 n-1개(최대 9999개)의 간선이 들어오지만 1167번의 경우 10만개가 넘는 간선이 들어올 수 있다.

따라서 시간초과가 나지 않는 다른 방법으로 해결해야 한다.

 

 

https://www.acmicpc.net/board/view/83695

 

위와 같은 접근 방법으로 해결 할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>


using namespace std;
typedef pair<int, int>P;
vector<P> adj[100001];
int dist[100001];
int maxLeng = 0;
int maxIdx;

void dfs(int root) {

	for (P next : adj[root]) {

		int node = next.first;
		int val = next.second;

		//방문한적있으면 스킵
		if (dist[node] != -1)continue;

		dist[node] = dist[root] + val;
		if (dist[node] > maxLeng) {
			maxLeng = dist[node];
			maxIdx = node;
		}

		dfs(node);
	}

}




int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V;
	cin >> V;



	for (int i = 0; i < V; i++) {
		int pa, ch = 0, val;
		cin >> pa;
		while (true) {
			cin >> ch;
			if (ch == -1)break;
			cin >> val;
			adj[pa].push_back(P(ch, val));
		}
	}

	fill(&dist[0], &dist[100001], -1);

	dist[1] = 0;
	dfs(1);

	fill(&dist[0], &dist[100001], -1);

	dist[maxIdx] = 0;
	dfs(maxIdx);

	cout << maxLeng;



}