Graph B1967

개요

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

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

계획한 풀이법

이전에 푼 문제와 사실상 똑같은 문제였다.
비교대상은 무엇이든 상관없으니 1로 시작하도록 하고 가장 가중치가 큰 정점을 찾아
그 정점을 DFS하면 최대 길이가 나오게 된다.

코드

#include <iostream>
#include <vector>
#include <stack>



using namespace std;
const int MAX = 10001;
//메모리 초과
vector<pair<int,int>> graph[MAX];
int N = 0;
bool visit[MAX];
int maxCost = 0;

int DFS(int startV)
{
	stack<pair<int,int>> s;
	s.push(make_pair(startV,0));
	int curV = 0;
	bool allVisited = false;
	int curCost = 0;
	int maxV = 0;

	while(s.size() != 0)
	{
		curV = s.top().first;
		if(!visit[curV])
		{
			curCost += s.top().second;

		}
		visit[curV] = true;
		allVisited = true;
		if(maxCost < curCost)
		{
			maxCost = curCost;
			maxV = curV;
		}
		for(int j=0;j<graph[curV].size();j++)
		{
			int nextV = graph[curV][j].first;
			if(visit[nextV])
			{
				continue;
			}
			int prevCost = graph[curV][j].second;
			s.push(make_pair(nextV, prevCost));
			allVisited = false;
			break;
		}
		if(allVisited)
		{
			curCost -= s.top().second;
			s.pop();
		}

	}
	return maxV;



}

void connectEdge(int v,int e,int cost)
{
	//cout << "V , E 연결\n";
	//cout << v << "," << e << "\n";

	graph[v].push_back(make_pair(e,cost));
	graph[e].push_back(make_pair(v,cost));

}

void init()
{
	cin >> N;
	int v,edge,cost;
	for(int i=0;i<N-1;i++)
	{
		cin >> v >> edge >> cost;
		connectEdge(v,edge,cost);
	}

}

void solve()
{
	int maxV = DFS(1);
	fill_n(visit,MAX,0);
	DFS(maxV);
	cout << maxCost;
}


int main()
{
	init();
	solve();




}

느낀 점

• 2시간 넘겨서 참고한 풀이가 바로 생각났는데 이래서는 내가 푼게 아닌 것 같은 기분이 들었다.
  하지만 여러가지 시도를 해보니 이 방법이 맞구나 체감이 되어서 곧 바로 풀었다.
  또 고집이 문제 풀이 시간을 눌렸다.
• 스스로가 생각한 풀이방법으로 풀린다면 얼마나 좋을까?
  하지만 그렇지 않은 경우가 앞으로 엄청나게 많을 것이다.
  그렇다고 기죽을 필요는 없는 것 같다.
  당연히 내가 잘하는 사람이 되기 전까지는 그 사람들의 뒷모습을 보는 것이 당연한 것이다.
  불만있으면 내가 잘하는 사람이 될때까지 더 열심히 해야 한다
• 지금은 결과주의자가 되자 문제를 빠르게 맞추는 것에만 집중하자
  아직은 직관을 배워야 할 것 같다.