백준 1967 C++

백준 1967

DFS로 두 번만 풀면 간단한 문제다.

트리는 결국 정점, 어떻게보면 가장 가운데에 있는 노드가 필연적으로 있을 수 밖에 없는 구조다. 받은 정보를 토대로 모든 간선을 연결해 준 후, 가장 가운데이자 루트노드인 1번에서 가장 먼 곳을 탐색한다.

그 1번에서 가장 먼 곳을 탐색하면, 그 곳이 제일 말단에 있는 것은 당연하니, 그 제일 말단에서 또 가장 먼 곳을 구하면 그게 트리의 지름(트리의 가장 길게 늘어나는 경우)이 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N, maxnode, maxdist;

struct node {
	int e, val;
};
vector<node> v1[10001];
bool visited[10001];

void dfs(int cur, int dist) {
	if (visited[cur]) return;//이미 방문한 노드 거르기.
	if (maxdist < dist) {//만약에 이번까지의 거리가 가장 먼 거리라면.
		maxdist = dist;//이번 거리를 가장 먼 거리라고 넣기.
		maxnode = cur;//이번 노드가 가장 먼 노드라고 넣기.
	}

	visited[cur] = true; //cur번 노드 방문햇다고 넣기.
	for (int x = 0; x < v1[cur].size(); x++) {//cur에 연결되어있는 노드들 탐색.
		int ncur = v1[cur][x].e;//cur번 노드에서 갈 수 있는 ncur노드.
		int ndist = v1[cur][x].val + dist;// cur까지 거리 + cur ~ ncur 거리.
		dfs(ncur, ndist);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int s, e, v;
	cin >> N;
	for (int x = 0; x < N-1; x++) {
		cin >> s >> e >> v;
		v1[s].push_back({ e,v });//간선 연결. 양방향 그래프.
		v1[e].push_back({ s,v });//간선 연결.
	}
	dfs(1, 0);//루트 노드(1)번에서 가장 먼 곳을 찾기. 
	memset(visited, false, sizeof(visited));//가장 먼 곳에서 또 탐색해야하니 초기화.
	maxdist = 0;//새로 탐색이니 maxdist를 초기화.
	dfs(maxnode, 0);//1번에서 가장 먼 곳을 찾기.
	cout << maxdist;
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기