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

풀이

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

using namespace std;
struct Edge {
	int to;
	int cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};

int n;
vector <Edge> A[100001];
bool check[100001];
int dist[100001];

void bfs(int start) {
	memset(dist, 0, sizeof(dist));
	memset(check, false, sizeof(check));
	queue <int> q;
	check[start] = true;
	q.push(start);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i=0; i<A[x].size(); i++) {	// A[x] 간선 리스트 크기만큼 반복
			Edge &e = A[x][i];
			if (check[e.to] == false) {
				dist[e.to] = dist[x] + e.cost;
				q.push(e.to);
				check[e.to] = true;
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	for (int i=0; i<n; i++) {	// n만큼 반복
		int a,b,c;
		cin >> a;
		while (1) {	// 무한 반복
			cin >> b;
			if (b == -1) break;
			cin >> c;
			A[a].push_back(Edge(b, c));	// A[a] 간선리스트에 Edge(b,c) 저장
		}
	}
	bfs(1);
	int start = 1;
	for (int i=2; i<=n; i++) {
		if (dist[i] > dist[start]) {	// 1~n의 dist 길이 비교
			start = i;
		}
	}
	bfs(start);
	int ans = dist[1];
	for (int i=2; i<=n; i++) {		// 1~n의 dist 길이 비교
		if (ans < dist[i]) {
			ans = dist[i];
		}
	}
	cout << ans;
	return 0;
}

개념

트리의 지름은 트리에 존재하는 모든 경로 중 가장 긴 것의 길이이다.

구하기 위해 두번의 탐색이 필요하다.

 

① 루트에서 가장 먼 정점인 A 정점까지 이동

② A에서 가장 먼 정점까지 이동

 

---

구조체 생성자 사용

Edge(int to, int cost) : to(to), cost(cost) {}

이는 생성자로, 구조체를 초기화 할 때 유용하다.

e.to = b; e.cost = c; 의 과정은 e = Edge(b, c); 로 대체될 수 있다. 

---

풀이

 

입력받기

 

정점의 개수만큼 반복이 진행된다.

첫번째인 노드번호 a를 받은뒤, while (1)을 사용한다.

b가 -1일 때 문장이 종료되므로, 이 무한 반복문 안에서 break 조건을 만든다.

다음노드 b와 가중치 c가 무사히 입력되면, A[n]에 push_back 해서 자료형 Edge로 b, c를 넣는다. 

간선리스트 형식

bfs

 

두번 탐색을 거쳐야하니, bfs 함수 내부에 memset으로 dist, check 배열을 초기화 한다.

start를 queue에 넣은뒤, queue가 빌 때까지 반복이 일어난다.

내부에서 A[x]의 크기만큼 반복하여 bfs를 진행하는데, Edge &e = A[x][i]; 를 통해 변수에 값을 저장한다.

e.to (다음 노드) 를 방문하지 않았을 때, 다음을 진행한다.

 

① dist[]를 이전 dist 값 + e.cost (다음 가중치) 로 초기화 한다. (sum 구하는 방식)

② queue에 e.to (다음 노드) 넣어줌

③ e.to (다음 노드)에 방문 표시

 

결과

 

정점번호는 1~N 까지 매겨진다.

1은 무조건 존재하므로, bfs(1) 을 진행한다.

 

탐색이 끝난 뒤, dist 배열에 길이 값들이 저장된다.

1부터 각 정점까지 어떤 dist[정점]이 가장 긴지 확인한다.

if문을 통해 가장 긴 값일 때의 정점을 start 변수에 대입한다.

왼쪽 : bfs(1)    오른쪽 : bfs(start)

이제 bfs(start)를 진행한다.

1부터 각 정점까지 어떤 dist[정점]이 가장 긴지 확인한다.

if문을 통해 가장 긴 값일 때의 길이를 ans에 대입한다.

 

 

※ 예시를 들어서 해봤는데, 1이 루트가 아니여도 문제가 없는 것 같다.