[BOJ] 1967 트리의 지름

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

Note

트리의 최대 지름을 출력해주자.

어떤 경우가 트리의 지름이 최대가 되는지를 생각하는 것이 가장 어려운문제.
질문 게시판에서 해답을 얻었던 문제.
루트노드에서 갈 수 있는 최장 거리 노드는 무조건 리프노드가 된다.
그렇다면 최장 거리에 있는 리프노드를 기준으로 가장 멀리 있는 다른 노드를 찾는다면 최장 지름을 얻을 수 있다.
해당 아이디어만 있으면 됬던 문제. 떠올리지 못했던 것이 조금 아쉽다.

알고리즘

1. 노드와 간선 정보를 입력 받는다.
2. 1번 노드(root Node)를 기준으로 가장 멀리있는 노드를 구한다.
3. 구해진 노드를 기준으로 다시한번더 가장 멀리 있는 노드를 구한다.
4. 두 노드의 거리를 출력한다.

소스코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const short NODE_MAX = 10000;

struct Node {
	short vertex;
	int weight;

	Node() {};
	Node(short v, int w) : vertex(v), weight(w) {};
};

Node parent[NODE_MAX];
vector<vector<Node>> child;

int getMaxNodeAtRoot() {

	bool check[NODE_MAX] = { true, };
	int maxLength = 0;
	int maxNode = 0;
	queue<Node> q;
	q.push(Node(0, 0));

	while (!q.empty())
	{
		Node cur = q.front();
		q.pop();

		if (cur.weight > maxLength) {
			maxLength = cur.weight;
			maxNode = cur.vertex;
		}

		for (int i = 0; i < child[cur.vertex].size(); i++) {
			Node childNode = child[cur.vertex][i];
			if (!check[childNode.vertex]) {
				check[childNode.vertex] = true;
				q.push(Node(childNode.vertex, cur.weight + childNode.weight));
			}
		}
	}

	return maxNode;
}

int solve(int start) {

	int res = 0;
	bool check[NODE_MAX] = {};
	queue<Node> q;
	q.push(Node(start, 0));
	check[start] = true;

	while (!q.empty()) {
		Node cur = q.front();
		q.pop();

		if (cur.weight > res) {
			res = cur.weight;
		}

		Node curParent = parent[cur.vertex];
		if (!check[curParent.vertex]) {
			check[curParent.vertex] = true;
			q.push(Node(curParent.vertex, cur.weight + curParent.weight));
		}

		for (int i = 0; i < child[cur.vertex].size(); i++) {
			Node childNode = child[cur.vertex][i];
			if (!check[childNode.vertex]) {
				check[childNode.vertex] = true;
				q.push(Node(childNode.vertex, cur.weight + childNode.weight));
			}
		}
	}

	return res;
}

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

	int nodeCount;
	cin >> nodeCount;

	child.resize(nodeCount);

	for (int i = 0; i < nodeCount; i++) {
		int par, chd, wei;

		cin >> par >> chd >> wei;

		child[par - 1].push_back(Node(chd - 1, wei));
		parent[chd - 1] = Node(par - 1, wei);
	}

	int maxAtRoot = getMaxNodeAtRoot();

	int res = solve(maxAtRoot);
	
	cout << res;

	return 0;
}

2019-04-21 18:25:55에 Tistory에서 작성되었습니다.