Graph B1167

개요

백준 문제 1167번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 2시간
https://www.acmicpc.net/problem/1167

문제

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

계획한 풀이법

처음엔 간단히 생각해서 그냥 입력받은 뒤 DFS하면 될 줄 알았지만
그렇지 않았다 왜냐하면 DFS는 가장 깊게 들어가게 되는데, 이 때 끝점과 시작점까지의 길이가 가장 긴 길이라고는 단정할 수 없다.
가중치는 가장 큰 값인 것이 분명하지만, 그것과 별개로 현재 시작점과 가중치가 가장 큰 정점이 가장 길지 않는 경우도 있기 때문이다.
그렇다면 가중치가 가장 높은 정점에서 DFS를 하게 되면 이때는 가중치가 가장 큰 정점이 시작점이니 여기서도 가장 큰 길이가 나오게 된다.

코드

#include <iostream>
#include <vector>

using namespace std;
const int MAX = 100001;

vector<pair<int, int> > graph[MAX];
bool visit[MAX];
int maxCost = 0;
int maxCostNode = 0;

int DFS(int startV,int cost)
{
	if(visit[startV])
	{
		return -1;
	}
	int result;
	visit[startV] = true;

	for(int i=0;i<graph[startV].size();i++)
	{	
		result = DFS(graph[startV][i].first,graph[startV][i].second+cost);
		if(result > maxCost)
		{
			maxCost = result;
			maxCostNode = graph[startV][i].first;
		}
	}
	return cost;

}

void connectEdge(int v,int e,int length)
{
	graph[v].push_back(make_pair(e,length));
}

void solve()
{

	int N = 0;
	cin >> N;

	int v = 0,e = 0,len = 0;
	for(int i=0;i<N;i++)
	{
		v = 0,e = 0,len = 0;
		cin >> v >> e;

		while(e != -1)
		{
			cin >> len;
			connectEdge(v,e,len);
			cin >> e;
			
		}
	}

	fill_n(visit,MAX,false);

	for(int i=1;i<=N;i++)
	{
		DFS(i,0);
	}
	maxCost = 0;
	fill_n(visit,MAX,false);
	DFS(maxCostNode,0);


	cout << maxCost;

}

int main()
{
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	solve();

}

느낀 점

• 이 문제는 다른 사람의 풀이를 참조하고 이해하여 문제를 풀었다.
• 문제를 읽고 떠오른 방법에 대한 검증을 깊게 해보자(너무 단순하게 생각하지 말자)