Beakjoon] 트리의 지름 구하기 (백준 1167 코테) - 탐색

---

🅰️문제주소 : https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

🚩문제 

 

🪡풀이 

 - 가장 긴 두 점 사이의 거리를 구하는 방법을 알아야 하는데 이는 임의의 어떤 한 점에서 가장 먼 곳의 위치를 찾아낸 후 그 위치로부터 가장 멀리 있는 곳까지의 거리로 구할 수 있다.
-  map을 그릴때 vector<vector<pair<int, long long>>> 으로 거리값도 함께 저장하면서 그린다.
- 방문여부 배열과, 누적 거리 배열을 만든다.
- 임의의 위치에서 BFS를 시작하고 누적거리 배열을 순회하며 가장 먼 곳의 노드위치로부터 한 번 더 BFS를 돌린다.

 

 

☕코드는 아래 숨김

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

std::vector<bool> V;
std::vector<long long> D;
std::vector<std::vector<std::pair<int, long long>>> MAP;

int N;

void BFS(int node) {
	std::queue<std::pair<int, long long>> bfsQ;
	//굳이 큐에 거리값을 가지고 있을 필요는 없었음...
	bfsQ.push(std::make_pair(node, 0));	
	V[node] = true;

	while (bfsQ.empty() == false) {
		int nodeNum = bfsQ.front().first;
		bfsQ.pop();
		for (int i = 0; i < MAP[nodeNum].size(); ++i) {
			if (V[MAP[nodeNum][i].first] == false) {
				bfsQ.push(std::make_pair(MAP[nodeNum][i].first, MAP[nodeNum][i].second));
				V[MAP[nodeNum][i].first] = true;		
				D[MAP[nodeNum][i].first] = D[nodeNum] + MAP[nodeNum][i].second;
			}		
		}		
		
	} 
}

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

	std::cin >> N;

	V = std::vector<bool>(N+1, false);
	MAP.resize(N+1);
	D.resize(N+1, 0);

	for (int i = 1; i <= N; ++i) {
		int num;
		std::cin >> num;
		while (true) {
			int first, second;
			std::cin >> first;
			if (first == -1)
				break;
			std::cin >> second;
			MAP[num].push_back(std::make_pair(first, second));
		}
	}

	BFS(2);
	long long max_distance = 0;
	int max_node = 0;

	for (int i =1; i<= N; ++i){
		if (max_distance < D[i])
		{
			max_distance = D[i];
			max_node = i;
		}
	}

	V.resize(0);
	D.resize(0);
	V.resize(N + 1, false);
	D.resize(N + 1, 0);
	BFS(max_node);
	
	for (int i = 1; i <= N; ++i) {
		if (max_distance < D[i])
		{
			max_distance = D[i];
		}
	}

	std::cout << max_distance;
	

	return 0;
}

 

💡알게 된 것 

 - 거리값을 줄 때 어떻게 접근해야 하는지(맵 그릴때 포함하며 BFS의 큐에선 노드 위치만)
 - 임의 위치에서 시작 할 때 큐에 시작 노드를 넣는 것을 빠뜨려서 거리를 구할 때 계산이 꼬였었었다. 시작노드도 꼭 넣어주기
- 트리의지름을 구하는 방법을 알게 됨.

---