[BOJ 14172] Moocast

https://www.acmicpc.net/problem/14172

14172번: Moocast

 

- 문제 요약

 

Farmer John의 N 소(1≤N≤200)는 그들 사이에서 중요한 메시지를 방송하기 위해 비상 "무캐스트" 시스템을 구성하려고 합니다.

소들은 먼 거리에서 서로 울부짖는 대신 소 한 마리당 하나씩 워키토키를 장착하기로 결정합니다. 이 워키토키는 각각 전송 반경이 제한되어 있습니다. 전력 P의 워키토키는 거리 P만큼 떨어진 다른 소에게만 전송할 수 있습니다(소 B가 할 수 없더라도 소 A는 소 B에게 전송할 수 있습니다. 암소 A의 전력이 암소 B의 전력보다 크기 때문에 다시 전송합니다. 다행히 소는 여러 홉으로 구성된 경로를 따라 서로 메시지를 전달할 수 있으므로 모든 소가 다른 모든 소에게 직접 전송할 수 있는 것은 아닙니다.

워키토키 전송의 비대칭 특성으로 인해 일부 젖소의 방송은 많은 수의 수신자에게 도달하는 능력(중계 고려)에서 다른 젖소보다 더 효과적일 수 있습니다. 암소가 한 마리의 암소에서 발생하는 브로드캐스트로 도달할 수 있는 최대 암소 수를 결정하도록 도와주세요.

 

 

- 알고리즘 정리

 

DFS 알고리즘을 활용하여 각각의 소가 다른 소에 연결되는 수를 저장하고, 방문 여부는 check[] 배열로 관리합니다.

만약 현재 다른 소에 연결된 수가 기존의 수보다 크다면 계속 갱신하며 최대값을 구합니다.

최대값은 ret 변수에 저장됩니다. (ret의 초기값은 1)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

struct st{
	int x,y,r;
};
int n;
vector<st>v;
bool check[201];

int f(int w){
	check[w]=true;
	int ret=1;
	int r2=v[w].r*v[w].r;
	for(int i=0;i<n;i++){
		int a=(v[w].x-v[i].x)*(v[w].x-v[i].x)+(v[w].y-v[i].y)*(v[w].y-v[i].y);
		if(!check[i]&&a<=r2){
			ret+=f(i);
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		v.push_back({a,b,c});
	}
	int result=0;
	for(int i=0;i<n;i++){
		memset(check,0,sizeof(check));
		result=max(result,f(i));
	}
	cout<<result;
}

코드 제출 결과