백준_트리의 지름길

[ 풀이 방법 ]

토큰이란걸 만들었다. 모든 토큰의 시작점은 트리의 단말노드이다. 토큰에는 현재 위치, 이전 위치, 총 이동거리의 정보를 포함하고 있다. 

이 토큰을 큐에 넣고 하나씩 빼면서 현재 위치에서 이동할 수 있는 모든 방향으로 퍼지게 만들었다(BFS 방법). 

이 때, 왔던 길로 다시 못가게 하기 위해서 토큰에 이전 위치를 저장했다. 이제 가려고하는 위치와 이전 위치가 같다면? 왔던길로 다시 돌아가는 거니까 못가게 막았다.

그리고 예외 상황이 문제를 짜증나게 만들었는데, 첫번째는 지름이 단말-단말 뿐만 아니라 단말-루트도 가능하다. 루트가 자식노드를 하나만 갖고 있으면 이런 경우가 가능하다. 

두번째는 단말노드를 큐에 넣으면 안된다. 1만개쯤의 노드가 있다면 단말노드는 수천개쯤 된다. 메모리가 뻑날 수 있기에 단말 노드는 큐에 않넣는다. 굳이 넣을 필요도 없다. 어차피 단말에 가면 탐색할 필요가 없으니까.

마지막으로 입력으로 들어오는 트리정보는 FindPar, FindChild 배열에 저장했는데, 이 배열의 역할은 다음과 같다.

노드 10의 자식을 찾을 때는 FindChild[10]을 이용하면 바로 찾을 수 있게 배열을 만들었다. 반대로 노드 10의 부모를 찾을 때는 FindPar[10]으로 찾을 수 있게 만들었다. 이때, 자식 노드는 여러 개일 수 있어서 벡터를 썼다. 그래서 실제로 FindChild[10][0], FindChild[10][1], FindChild[10][2]처럼 자식에 접근할 할 수 있게 만들었다.

[ 나의 코드 ]

#include <iostream>
#include <queue>
#include <vector>
#define MAX 10001
using namespace std;
typedef struct node
{
	int num, dist;
}node;
typedef struct token
{
	int num, pre, tDist;
}token;
int N, dia;
vector<node> FindChild[MAX];
node FindPar[MAX];
queue<token> q;
void InData()
{
	int par, child, dist;
	node data;
	token ter;
	cin >> N;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> par >> child >> dist;
		
		data.num = child; data.dist = dist;
		FindChild[par].push_back(data);
		data.num = par;
		FindPar[child] = data;
	}
	for (int i = 1; i <= N; i++)
	{
		if (FindChild[i].size() == 0)
		{
			ter.num = i; ter.tDist = ter.pre = 0;
			q.push(ter);
		}
	}
}
void MaxDia(int a)
{
	if (a > dia)
		dia = a;
}
int main()
{
	token cur, next;
	InData();
	while (!q.empty())
	{
		cur = q.front();
		q.pop();
		// 부모 노드로 이동
		next.num = FindPar[cur.num].num;
		if (next.num != 0 && next.num != cur.pre)
		{
			next.pre = cur.num;
			next.tDist = cur.tDist + FindPar[cur.num].dist;
			MaxDia(next.tDist);
			q.push(next);
		}
		// 자식 노드로 이동
		for (int i = 0; i < FindChild[cur.num].size(); i++)
		{
			next.num = FindChild[cur.num][i].num;
			// 왔던 길로는 안간다.
			if (next.num != cur.pre)
			{
				next.pre = cur.num;
				next.tDist = cur.tDist + FindChild[cur.num][i].dist;
				// 단말 노드는 더 탐색할 필요 없다.
				if (FindChild[next.num].size())
					q.push(next);
				else
					MaxDia(next.tDist);
			}
		}
	}
	cout << dia << endl;
	return 0;
}