백준 1167 트리의 지름

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

1967번: 트리의 지름

노드간의 가중치가 주어질 때 각 노드간의 최대 길이를 구하는 문제이다. 이 문제는 트리도 결국 그래프와 다르지 않다는 것을 인지하는 것에서 시작한다. 아래 사진을 보면 좀 더 이해가 갈 것이다. 

 

 

 

처음에는 각 노드별 다익스트라로 최대 길이를 구했는데 시간 초과가 발생했다. 그래서 다른 방법을 찾아보는 도중 bfs, dfs를 이용하는 방법을 찾았다. 

 

1. 임의의 노드에서 bfs, dfs를 사용하여 최대 길이 인 노드를 찾는다.

2. 해당 노드를 시작으로 다시 bfs, dfs를 사용하여 최대 길이인 노드를 찾고 그 길이가 최장 길이이다.

 

 

dfs

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N;
vector <pair<int, int> > map[100002];

int visited[100002];
int maxDistance;
int maxIndex;
void input();
void dfs(int index, int cost);


int main(){
	input();
	dfs(1, 0);

	for(int i = 1; i <= N; i++)
		visited[i] = 0;
	maxDistance = 0;

	dfs(maxIndex, 0);
	printf("%d", maxDistance);
}

void input(){
	int starter, end, distance; 
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d", &starter);
		for(;;){
			scanf("%d", &end);
			if(end==-1)
				break;
			
			scanf("%d", &distance);
			
			map[starter].push_back(make_pair(end, distance));
			map[end].push_back(make_pair(starter, distance));
		}
	}
}

void dfs(int index, int cost){
	if(visited[index] != 0)
		return ;

	if(maxDistance < cost){
			maxDistance = cost;
			maxIndex = index;
	}

	visited[index] = 1;

	for(int i = 0; i < map[index].size(); i++){
		pair<int, int> next = map[index][i];
		int nextIndex = next.first;
		int nextWeight = next.second;
		dfs(nextIndex, nextWeight + cost);
	} 
}

 

bfs

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector <pair<int, int> > map[100002];
queue <int> qu;

int maxDistance;
void input();
int bfs(int index);

int main(){
	input();
	bfs(bfs(1));
	printf("%d", maxDistance);
}

void input(){
	int starter, end, distance; 
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d", &starter);
		for(;;){
			scanf("%d", &end);
			if(end==-1)
				break;
			
			scanf("%d", &distance);
			
			map[starter].push_back(make_pair(end, distance));
			map[end].push_back(make_pair(starter, distance));
		}
	}
}

int bfs(int index){
	qu.push(index);
	int visited[100002] = {0, };
	int result[100002] = {0, };
	int maxPoint = 0;
	int max = 0;
	while(!qu.empty()){
		int starter = qu.front();
		qu.pop();
		visited[starter] = 1;
		for(int i = 0; i < map[starter].size(); i++){
			pair<int, int> next = map[starter][i];
			int nextPoint = next.first;
			int distance = next.second;
			if(visited[nextPoint] == 0 && result[nextPoint] < distance + result[starter]){
				result[nextPoint] = distance + result[starter];
				qu.push(nextPoint);
				if(max < result[nextPoint]){
					maxPoint = nextPoint;
					max = result[nextPoint];
				}
			}
		}
	}

	maxDistance = *max_element(result, result+N+1);
	return maxPoint;
}