글 읽기 - [힌트] 문제 접근 방법과 아이디어, 소스코드 입니다,

helios789789 3년 전 0

일반적인 BFS 나 위상정렬 등의 트리 이론으로는 N^2 의 시간복잡도가 나오기떄문에 1만개의 정점에 대해 시간안에 통과할 수 없습니다.

https://jason9319.tistory.com/303

위의 블로그에서 잘 설명해주시고 있는 트리의 지름 이라는 개념을 사용해야 합니다.

트리의 지름이란, 트리 내에 서 가장 먼 정점 두개 사이의 거리 를 말합니다.

이 문제에서 요구하는 사항과 트리의 지름의 정의가 일치합니다!

트리의 지름이란 개념을 모르고 접근해서 많이 해맸던 문제네요.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <string.h>
#include <math.h>
#include <cassert>
#include <limits.h>
#pragma warning(disable:4996)
using namespace std;


const int INF = 987654321;
int n;

vector<int> adj[10001];
int ret = INF;

int maxVal = 0;
int maxIdx = 0;

int cost[10001];

vector<int> starts;
vector<pair<int, int>> ends;

void dfs(int here, int prev, int c) {
	
	if (maxVal < c) {
		maxVal = c;
		starts.clear();
		starts.push_back(here);
	}
	else if (maxVal == c) {
		starts.push_back(here);
	}

	for (auto& next : adj[here]) {
		if (next == prev)
			continue;

		dfs(next, here, c + cost[next]);
	}
}

// 트리의 지름 위의 출발 정점에서 가능한 도착 정점들을 탐색
void dfs2(int here, int prev, int c, int origin_start) {

	if (maxVal < c) {
		maxVal = c;
		::ends.clear();

		if (origin_start < here)
			::ends.push_back({ origin_start, here });
		else
			::ends.push_back({ here, origin_start });
	}
	else if (maxVal == c) {
		if (origin_start < here)
			::ends.push_back({ origin_start, here });
		else
			::ends.push_back({ here, origin_start });
	}

	for (auto& next : adj[here]) {
		if (next == prev)
			continue;

		dfs2(next, here, c + cost[next], origin_start);
	}
}


void solve() {
	dfs(1, 1, cost[1]);

	maxVal = 0;

	for (auto& s : starts)
		dfs2(s, s, cost[s], s);

	sort(::ends.begin(), ::ends.end());

	cout << maxVal<< " "<< ::ends[0].first << endl;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> cost[i + 1];

	for (int i = 0; i < n-1; i++) {
		int start, end;
		cin >> start >> end;
		adj[start].push_back(end);
		adj[end].push_back(start);
	}
		
	solve();

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[힌트] 문제 접근 방법과 아이디어, 소스코드 입니다,

helios789789 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말