(C++) [백준 1167번] 트리의 지름

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

1167번: 트리의 지름

글에 앞서, 트리의 지름을 구하는 방법이 있다.

 

https://blog.myungwoo.kr/112 

트리의 지름 구하기

 

 

 

[풀이]

결국 트리의 지름 구하기는 임의의 점 x에서 가장 긴 점 y를 구하고, y에서 가장 긴 점 z를 구한 다음 y-z 사이의 거리를 구하는 문제이다.

V가 10만이므로 인접 행렬로는 메모리 초과가 떠서 풀 수 없고 인접 리스트를 사용해야 한다.

그래프라면 완전 그래프의 경우의 최대 간선 수는 V * (V-1) / 2이므로 인접 리스트여도 풀 수 없겠지만 트리의 경우 최대 간선수가 V-1개이므로 인접 리스트로 풀 수 있다. (도움 알빡방 류호석님)

 

내 경우 인접 리스트 대신 10만개의 벡터 배열을 사용해 벡터의 i번째 인덱스를 트리의 시작 정점으로 사용했다.*이때 중요한 부분은 예제 입력은 항상 정점 번호 오름차순으로 입력이 들어오지만 테스트 케이스의 경우는 항상 정점 번호 오름차순으로 들어온다는 보장이 없다는 것이다. 무작정 for문의 인덱스를 배열 인덱스로 사용하면 틀린 답이 된다. 정점 번호를 따로 입력으로 주는것에 유의해야 한다.

	for (int i = 1; i <= v; i++)
	{
		cin >> t;
		while (true)
		{
			cin >> Vertex;
			if (Vertex == INF)
				break;
			cin >> Weight;
			Input.Vertex = Vertex;
			Input.Weight = Weight;
			Graph[t].push_back(Input);
		}
	}

또한 이를 위해 데이터와 인덱스를 가지는 구조체를 정의하여 사용했다.

typedef struct Tree
{
	int Vertex;
	int Weight;
}Tree;

트리의 지름은 임의의 점 x에서 가장 긴 거리를 가진 점 y를 구하고, y에서 z를 구한 다음 z-y까지의 거리를 구해야 하므로, DFS로 풀 수 있다.

int DFS(int End, int Cost)
{
	Tree Input;
	while (!(DfsStack.empty()))
	{
		int Index = DfsStack.top().Vertex;
		int Weight = DfsStack.top().Weight;
		DfsStack.pop();
	
		for (int j = 0; j < Graph[Index].size(); j++)
		{
			if ((visited[Graph[Index][j].Vertex]))
				continue;
			visited[Graph[Index][j].Vertex] = true;
			Input.Vertex = Graph[Index][j].Vertex;
			Input.Weight = Graph[Index][j].Weight;
			DfsStack.push(Input);
			DFS(End, Cost + Graph[Index][j].Weight);
		}
		if (MaxWeight < Cost)
		{
			MaxVertex = Index;
			MaxWeight = Cost;
		}
		visited[Index] = false;
	}
	return 0;
}

DFS는 스택을 이용하므로 스택에 원소 하나를 넣고 Graph[i](시작 정점)에서 아직 방문하지 않은 정점을 찾아 스택에 넣고 재귀적으로 호출하면 된다. 만약 스택이 비었을때(DFS가 종료) 가중치가 현재 내 가중치보다 높다면 값을 변경해주고 이때의 인덱스를 저장함으로써 가장 긴 거리를 가진 점을 구할 수 있다.

DFS를 호출한 스택에서 visited[Index]를 false로 바꿔주지 않으면 다음에 방문해야하는 정점을 방문하지 못 할 수도 있으므로 항상 visited의 처리에 주의해야 한다.

 

[전체 코드]

#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
#define INF -1

typedef struct Tree
{
int Vertex;
int Weight;
}Tree;
bool visited[MAX];
vector <Tree> Graph[MAX];
stack <Tree> DfsStack;
int MaxWeight, MaxVertex;
int DFS(int End, int Cost)
{
Tree Input;
while (!(DfsStack.empty()))
{
int Index = DfsStack.top().Vertex;
int Weight = DfsStack.top().Weight;
DfsStack.pop();

for (int j = 0; j < Graph[Index].size(); j++)
{
if ((visited[Graph[Index][j].Vertex]))
continue;
visited[Graph[Index][j].Vertex] = true;
Input.Vertex = Graph[Index][j].Vertex;
Input.Weight = Graph[Index][j].Weight;
DfsStack.push(Input);
DFS(End, Cost + Graph[Index][j].Weight);
}
if (MaxWeight < Cost)
{
MaxVertex = Index;
MaxWeight = Cost;
}
visited[Index] = false;
}
return 0;
}
int solve(int y,int z)
{
for (int j = 0; j < Graph[z].size(); j++)
{
DfsStack.push(Graph[z][j]);
visited[z] = true;
visited[Graph[z][j].Vertex] = true;
DFS(y, Graph[z][j].Weight);
//fill_n(visited, MAX, false);
visited[Graph[z][j].Vertex] = false;
}
return 0;
}
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(0);
int v, x, y, z, t;
int Weight, Vertex;
Tree Input;
cin >> v;
for (int i = 1; i <= v; i++)
{
cin >> t;
while (true)
{
cin >> Vertex;
if (Vertex == INF)
break;
cin >> Weight;
Input.Vertex = Vertex;
Input.Weight = Weight;
Graph[t].push_back(Input);
}
}

x = 1;
solve(INF, x);

y = MaxVertex;
fill_n(visited, MAX, false);
solve(INF, y);
z = MaxVertex;
fill_n(visited, MAX, false);
solve(y, z);

cout << MaxWeight;
}