백준 1167 - 트리의 지름(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

DFS를 이용한 문제였습니다.

1번 정점에서 시작해서 가장 긴 거리에 있는 점을 찾은 뒤, 해당 점에서 되돌아오면서 길이를 재는 방법이였습니다.

문제 조건

출력 예시

해당 문제는 두번의 DFS를 사용해야하는 문제였습니다.

1~N번까지의 점 중에서 임의의 점을 하나 선택합니다.

해당 점에서 가장 거리가 먼 점을 하나 확인합니다. 이 점을 X라 하겠습니다.(저는 1번을 임의로 정했습니다.)

 

X점에서 다시 최장 길이를 구합니다. -> 트리의 지름입니다.

 

 

최장거리 구하는 코드

void dfs(int x, int cnt) {
	if (ans < cnt) {
		ans = cnt;
		finish = x;
	}
	for (int i = 0; i < line[x].size(); i++) {
		int X = line[x][i].first;
		int Y = line[x][i].second;
		if (check[X] == 0) {
			check[X] = 1;
			dfs(X, cnt + Y);
		}
	}
}

x번 정점에서 시작해 연결된 점들을 모두 찾습니다. 이전에 방문하지 않았던 점들만 방문하여 길이의 최댓값을 구합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int N;
vector<pair<int, int>> line[100001];
int ans;
int check[100001];
int finish;

void input(int x) {
	while (1) {
		int X, Y;
		scanf("%d", &X);
		if (X == -1) break;
		scanf("%d", &Y);
		line[x].push_back(make_pair(X, Y));
	}
}

void dfs(int x, int cnt) {
	if (ans < cnt) {
		ans = cnt;
		finish = x;
	}
	for (int i = 0; i < line[x].size(); i++) {
		int X = line[x][i].first;
		int Y = line[x][i].second;
		if (check[X] == 0) {
			check[X] = 1;
			dfs(X, cnt + Y);
		}
	}
}

void solve() {
	check[1] = 1;
	dfs(1, 0);
	memset(check, 0, sizeof(check));
	ans = 0;
	check[finish] = 1;
	dfs(finish, 0);
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		int X;
		cin >> X;
		input(X);
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요