[ C++ 백준 1167, 1967 ] 트리의 지름, 트리의 지름

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

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

 

1167 문제를 풀었는데, 1967 또한 똑같은 코드에서 살짝 수정해서 해결이 되는 문제이다.

 

1167 코드

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

vector<pair<int, int>> vertexInfos[100001];
// vertexNum, length
int vertexSize = 0;
int maxVertex = 0;
unsigned long long answer = 0;

bool visited[100001];
int DP[100001];

void InputVertexInfo();
void DFS(int vertexNum, int dist)
{
	if (visited[vertexNum])
		return;

	if (answer < dist)
	{
		answer = dist;
		maxVertex = vertexNum;
	}

	visited[vertexNum] = true;

	for (int i = 0; i < vertexInfos[vertexNum].size(); i++)
	{
		int nextIndex = vertexInfos[vertexNum][i].first;
		int nextDist = vertexInfos[vertexNum][i].second;
		DFS(nextIndex, nextDist + dist);
	}
}

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

	cin >> vertexSize;

	InputVertexInfo();
	
	DFS(1, 0);
	memset(visited, 0, sizeof(visited));
	answer = 0;
	DFS(maxVertex, 0);

	cout << answer;

}

void InputVertexInfo()
{

	for (int i = 0; i < vertexSize; ++i)
	{

		int inputNum, length;
		int vertexNum = 0;

		cin >> inputNum;
		vertexNum = inputNum;

		while (true)
		{
			cin >> inputNum;

			if (inputNum == -1)
				break;

			cin >> length;

			vertexInfos[vertexNum].push_back({inputNum, length});

		}

	}

}

 

 

1967

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

vector<pair<int, int>> vertexInfos[100001];
// vertexNum, length
int vertexSize = 0;
int maxVertex = 0;
unsigned long long answer = 0;

bool visited[100001];
int DP[100001];

void InputVertexInfo();
void DFS(int vertexNum, int dist)
{
	if (visited[vertexNum])
		return;

	if (answer < dist)
	{
		answer = dist;
		maxVertex = vertexNum;
	}

	visited[vertexNum] = true;

	for (int i = 0; i < vertexInfos[vertexNum].size(); i++)
	{
		int nextIndex = vertexInfos[vertexNum][i].first;
		int nextDist = vertexInfos[vertexNum][i].second;
		DFS(nextIndex, nextDist + dist);
	}
}

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

	cin >> vertexSize;

	InputVertexInfo();

	DFS(1, 0);
	memset(visited, 0, sizeof(visited));
	answer = 0;
	DFS(maxVertex, 0);

	cout << answer;

}

void InputVertexInfo()
{

	for (int i = 0; i < vertexSize - 1; ++i)
	{

		int inputNum, length;
		int vertexNum = 0;

		cin >> inputNum;
		vertexNum = inputNum;

		cin >> inputNum;
		cin >> length;

		vertexInfos[vertexNum].push_back({ inputNum, length });
		vertexInfos[inputNum].push_back({ vertexNum, length });

	}

}

 

모든 정점에서 탐색 시에는 시간 초과가 걸린다.

그렇다고 하나의 정점에서만 탐색하기에는 결과값이 다르게 나온다.

 

해결 방법은

1 정점부터 가장 먼 정점 탐색 후, 가장 먼 정점에서 다시 탐색해 지름을 알아내는 방식으로 진행하면 해결된다.

 

어느 정점이든 가장 먼 정점을 탐색하면, 그 정점은 서로 거리가 가장 먼 정점 중 하나의 정점이기에 그 정점에서 다시 탐색을 진행하면 해결이 되는 방식이다.