백준1967 - 트리의 지름

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

1967번: 트리의 지름

트리를 이용한 bfs 문제였다. 트리의 단말 노드에서 다른 단말 노드로 이동하기까지 소요되는 비용이 가장 큰 루트를 찾아서 출력하면 된다.

 

트리의 노드간의 관계를 입력하는데 각각의 노드는 양방향으로 입력해준다. 노드의 갯수가 많아서 push_back()보다 효율적인 emplace_back()을 사용하였다.

 

n개의 노드를 탐색하는 도중에 자식이 없는 단말노드를 만나면 바로 위에 노드부터 bfs를 이용하여 탐색을 진행한다.

 

bfs는 각각의 자식 노드에 대하여 탐색을 진행하고 단말 노드를 만나면 총 사용한 비용을 조사했던 가장 큰 비용과 비교한 뒤에 큰 비용으로 교체한다.

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define MAX 10001
using namespace std;

int n; //노드의 갯수
int a, b, c; //출발지 a, 도착지 b, 비용 c
int big = -1; //지름 중에 가장 큰 비용
vector<pair<int,int>> v[MAX]; //a에서 b로 가는 비용은 c이다.
bool visit[MAX]; //노드 방문 여부

//지름을 찾는 과정은 bfs로 한다.
void bfs(int x, int y) {
	queue<pair<int, int>> q; //first까지 이동하는데 총 사용한 비용은 seconddlek.
	q.push(pair<int, int>(x, y)); //첫번째 노드의 위치와 비용을 삽입
	visit[x] = true; //방문처리

	while (!q.empty()) {
		//첫번째 원소 추출하고 삭제
		x = q.front().first;
		y = q.front().second;
		q.pop();

		if (v[x].size() == 1) { //자식이 하나도 없는 노드를 만나면
			big = max(big, y); //찾은 지름 중에 큰 지름 찾기
			continue; //다음 노드로 이동
		}

		for (int i = 0; i < v[x].size(); i++) { //x노드의 자식 노드를 탐색 
			if (!visit[v[x][i].first]) { //방문하지 않은 자식 노드이면
				q.push(pair<int, int>(v[x][i].first, y + v[x][i].second)); //큐에 삽입
				visit[v[x][i].first] = true; //방문처리
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> c;

		//항상 양방향으로 이동한다고 가정하고 큐에 삽입
		v[a].emplace_back(pair<int, int>(b, c));
		v[b].emplace_back(pair<int, int>(a, c));
	}

	for (int i = 1; i <= n; i++) {
		if (v[i].size() == 1) { //자식 노드가 없는 노드이면
			memset(visit, false, sizeof(bool) * (n + 1)); //모든 노드를 미방문처리
			visit[i] = true; //출발지를 방문처리
			bfs(v[i][0].first, v[i][0].second); //출발지 바로 아래 자식에서 bfs탐색 시작
		}
	}

	cout << big;
}