FORTRESS - 요새 (트리)

https://algospot.com/judge/problem/read/FORTRESS

트리의 지름을 구하는 문제. 임의의 한 점에서 가장 먼 점u, u에서 가장 먼 점v에 대해 u~v거리구하면된다.

 

<문제설명>

서로가 서로에게 포함되거나 포함하는 원들이 최대 100개 주어진다.(겹치거나 접하는 경우 없음) 이때 임의의 두 점 사이에 건너야 하는 벽의 최대 개수를 구해라.

 

<풀이>

큰 원u가 작은원 v를 포함하는 것을 u->v라 할때 전체 형태는 트리의 형태가 된다.

 

간선을 이어줄때, 예를들어 a->b->c 인 경우 a->c를 잇지 않도록 주의한다. 반지름을 기준으로 오름차순 정렬하여 적절히 처리해주면 된다.

 

그리고 트리의 지름을 구하면 된다.

 

 

<코드>

간선을 이어주는 부분

for (int i = 0,x,y,r; i < n; i++) {
	cin >> x >> y >> r;
	ver[i] = make_tuple( x,y,r );
}
sort(ver, ver + n, [](V u, V v) {
	return get<2>(u) < get<2>(v);
	});	

for (int i = 0; i < n - 1; i++) {
	for (int j = i + 1; j < n; j++) {
		int xu, yu, ra, xv, yv, rb;
		tie(xu, yu, ra) = ver[i];
		tie(xv, yv, rb) = ver[j];
		if (dist(i, j) <= (ra - rb) * (ra - rb)) {
			adj[i].push_back(j);
			adj[j].push_back(i);
			break;
		}
	}
}

 

인접리스트를 기반으로 트리의 지름을 구하는 부분

int dfs(int u) {
	vst[u] = true;
	int ret = u;
	d[u] = 0;

	for (int v : adj[u]) 
		if (!vst[v]) {
			int ret_next = dfs(v);
			if (d[u] < d[v] + 1) {
				d[u] = d[v] + 1;
				ret = ret_next;
			}
		}
		
	return ret;
}

d[u]는 u와 가장 먼 점으로 부터 u까지의 거리이다.

dfs는 가장 먼 점의 정점을 반환하도록 한다. 인접한 정점 v에 대해 v에서 가장 먼 정점의 번호를 ret_next이라 한다. 

d[u]가 더 큰 값으로 갱신될 때 가장 먼 점을 갱신해준다.

 

 

좀 더 간단히 코드를 짜보면

dfs(u,prv,d) : 현재정점u, 이전 정점 prv, 시작점~현재점까지의 거리 d일 때, 시작점으로부터 가장 먼 점까지의 거리를 의미하는 전역변수 dst와 시작점으로부터 가장 먼 점 st를 갱신하는 void타입의 함수

 

현재 정점까지의 거리가 dst보다 클 때마다 dst와 st를 갱신한다.

void dfs(int u, int prv, int d) {
	if (dst < d) {
		dst = d;
		st = u;
	}
	for (int v : adj[u]) 
		if (v!=prv) 
			dfs(v, u, d + 1);
}

 

<전체코드>

typedef pair<int, int> P;
typedef tuple<int, int, int> V;
const int MAX = 1e2 + 2;

int n, st, dst;
vector<int> adj[MAX];
V ver[MAX];
bool vst[MAX];

double dist(int u, int v) { //거리 제곱
	int xu, yu, aa, xv, yv, bb;
	tie(xu, yu, aa) = ver[u];
	tie(xv, yv, bb) = ver[v];
	return (xu - xv) * (xu - xv) + (yu - yv) * (yu - yv);
}

void dfs(int u, int prv, int d) {
	if (dst < d) {
		dst = d;
		st = u;
	}
	for (int v : adj[u]) 
		if (v!=prv) 
			dfs(v, u, d + 1);
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		for (int i = 0; i < MAX; i++) adj[i].clear();
		cin >> n;
		for (int i = 0,x,y,r; i < n; i++) {
			cin >> x >> y >> r;
			ver[i] = make_tuple( x,y,r );
		}
		sort(ver, ver + n, [](V u, V v) {
			return get<2>(u) < get<2>(v);
			});	

		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				int xu, yu, ra, xv, yv, rb;
				tie(xu, yu, ra) = ver[i];
				tie(xv, yv, rb) = ver[j];
				if (dist(i, j) <= (ra - rb) * (ra - rb)) {
					adj[i].push_back(j);
					adj[j].push_back(i);
					break;
				}
			}
		}

		dst = 0; dfs(0,-1,0);
		dst = 0; dfs(st, -1, 0);
		cout << dst << '\n';
	}
}

 

<생각>

ps처음시작할 때 접했던 주제. 다시보니 새롭다