[C/C++] 백준 - 1167번 : 트리의 지름

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

1167번: 트리의 지름

문제

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

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

 

이 문제의 최대 V는 100,000이기 때문에 완전 탐색으로 모든 정점에서 가장 먼 노드까지의 거리를 구하려고 하면 시간초과가 발생한다. 나도 맨 처음에 다른 방법이 떠오르지 않아 완전탐색으로 구현했지만 시간초과가 났다.

하지만 다른 방법이 떠오르지 않아 결국 해결책을 구글링 했다.

 

찾아보니 트리의 지름은 누군가에 의해 증명되어 있다.

트리의 지름을 검색해보면

트리에서 가장 먼 거리의 두 지점을 이은 거리가 그 트리의 지름이다. 아무 지점이나 잡고, 그 지점에서 가장 먼 지점을 구하고, 그 지점에서 가장 먼 곳까지의 거리가 트리의 지름이다.

라고 나온다. 그래서 위 말대로 구현해주었고 맞을 수 있었다.. 

하나의 임의의 정점을 기준으로 가장 먼 지점의 정점을 구하고 그 정점에서 가장 먼 곳까지의 길이가 트리의 지름이 되는것이다.

 

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define endl '\n'

using namespace std;
typedef struct GraphNode {
	int dest;
	int cost;
	GraphNode* next;
}GraphNode;

typedef struct Graph {
	int Cnt;
	GraphNode* adj;
}Graph;

int maxNode, maxLen;
int answer[100003];
bool visited[100003];
priority_queue<int, vector<int>, greater<int>> pq;

void Init_Graph(Graph* gph, int Count) {
	gph->Cnt = Count;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (Count+1));
	for (int i = 1; i <= Count; i++) gph->adj[i].next = NULL;
}

int AddlinkedDirectEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1; 
}

void dfs(Graph* gph, int start) {
	while (!pq.empty()) {
		int y = pq.top();
		int prev = answer[y];
		pq.pop();

		GraphNode* head = gph->adj[y].next;
		while (head) {
			if (!visited[head->dest] && answer[head->dest] < head->cost + prev) {
				answer[head->dest] = head->cost + prev;
				visited[head->dest] = true;
				pq.push(head->dest);

				if (maxLen < answer[head->dest]) {
					maxLen = answer[head->dest];
					maxNode = head->dest;
				}
			}
			head = head->next;
		}
	}
}


int main() {
	CUNLINK;
	Graph graph;
	int V;
	cin >> V;
	Init_Graph(&graph, V);
	for (int i = 0; i < V; i++) {
		int Node, Link, Edge;
		cin >> Node;
		while (1) {
			cin >> Link;
			if (Link == -1) break;
			cin >> Edge;
			AddlinkedDirectEdge(&graph, Node, Link, Edge);
		}
	}
	memset(answer, -1, sizeof(answer));
	pq.push(1); answer[1] = 0; maxNode = 1; maxLen = 0; visited[1] = true;
	dfs(&graph, 1);
	
	memset(answer, -1, sizeof(answer));
	memset(visited, false, sizeof(visited));
	pq.push(maxNode); answer[maxNode] = 0; maxLen = 0;
	visited[maxNode] = true;
	dfs(&graph, maxNode);
	cout << maxLen << endl;

	return 0;
}