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

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

1967번: 트리의 지름

DFS를 사용하여 푸는 문제입니다.

임의의 점을 하나 선택한 뒤, 해당 점에서 다시 탐색을 하여 답을 구하는 문제였습니다.

문제 조건

출력 예시

1 ~ N까지의 정점이 있을 때, 가장 긴 노드 사이의 거리를 구하는 문제였습니다.

1번 점부터 N번 점까지 모든 경우를 확인하기에는 경우가 너무 많아 시간 초과가 생길 수 있습니다.

 

따라서 다른 방법을 통해 지름을 구해야하는데 그중 한 방법이 DFS를 2번 구하는 방법입니다.

 

먼저 1 ~ N번 정점중 하나를 고릅니다. 해당 점에서 가장 긴 거리를 가진 정점을 DFS를 통해 구합니다.

구한 점에서 다시 DFS를 통해 가장 긴 점을 구합니다. 이를 통해 가장 긴 트리의 지름을 구할 수 있습니다. 

해당 그림을 통해 쉽게 이해할 수 있습니다.

 

 

가장 긴 노드를 찾는 DFS를 구현하기

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[10001];
int ans;
int check[10001];
int finish;

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, next_X, Y;
		scanf("%d %d %d", &X, &next_X, &Y);
		line[X].push_back(make_pair(next_X, Y));
		line[next_X].push_back(make_pair(X, Y));
	}
	solve();
	return 0;
}

 

 

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