Moocast

알고리즘 구분 : BFS

문제

Farmer John's N cows (1≤N≤200) want to organize an emergency "moo-cast" system for broadcasting important messages among themselves.

Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius -- a walkie-talkie of power P can only transmit to other cows up to a distance of P away (note that cow A might be able to transmit to cow B even if cow B cannot transmit back, due to cow A's power being larger than that of cow B). Fortunately, cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow.

Due to the asymmetrical nature of the walkie-talkie transmission, broadcasts from some cows may be more effective than from other cows in their ability to reach large numbers of recipients (taking relaying into account). Please help the cows determine the maximum number of cows that can be reached by a broadcast originating from a single cow.

입력
The first line of input contains N.

The next N lines each contain the x and y coordinates of a single cow ( integers in the range 0…25,000) followed by p, the power of the walkie-talkie held by this cow.

출력
Write a single line of output containing the maximum number of cows a broadcast from a single cow can reach. The originating cow is included in this number.

예제 입력 1
4
1 3 5
5 4 3
7 2 1
6 1 1
예제 출력 1
3

문제 풀이

문제를 해석해보면, 각 소의 위치가 x, y 좌표로 주어지며, 각 소는 무전기를 가지고 있고, 무전기별로 전송 거리가 정해져있는 상태에서, 한 소에서 전송을 시작했을 때 최대 몇 마리의 소까지 전송이 가능한지를 구하라고 한다. 여기서 전송은 전송의 송신자의 전송 거리만 영향을 미치며, 수신자의 전송 거리는 영향을 미치지 않는다고 한다. 추가로, 1번 소에서 2번 소로 전송이 되면, 2번 소에서 전송할때는 1번 소의 전송 거리가 아닌 2번 소의 전송 거리를 기준으로 하여 전송 가능 여부를 확인해야 한다. 전송 거리는 반경 형식으로 주어지기에 소를 중심으로 전송 거리가 반지름인 원의 형태가 전송 가능 반경이 된다. 그렇기에, 이는 pow함수를 이용하여 피타고라스를 활용하여 비교할 수 있도록 하면 된다. 최대를 찾아야 하기에 시작점을 모든 소를 한 번씩 시도해보아야 하며, 시도할 때마다 거리 계산을 계속하면서 가능 여부를 확인할 경우, 시간 복잡도의 낮은 효율성을 불러오기에, 2차원 배열을 생성하여 도달 가능 여부를 한 번만 확인한 후, 해당 배열에서 값을 조회하는 방식으로 구현하였다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n;
struct node {
	int x;
	int y;
	int p;
};
vector<node> graph;
bool enable[201][201]; // 해당 각 IDX의 도달 여부 확인
int distance(int x1, int y1, int x2, int y2);
int bfs(int start);
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		node temp;
		cin >> temp.x >> temp.y >> temp.p;;
		graph.push_back(temp);
	}
	
	solve();
	
	return 0;
}

int distance(int x1, int y1, int x2, int y2) {
	int x, y;
	
	x = abs(x1 - x2);
	x = pow(x, 2);
	y = abs(y1 - y2);
	y = pow(y, 2);
	
	return x + y;
}

int bfs(int start) {
	int cnt, now;
	bool use[n];
	queue<int> q;
	
	memset(use, 0, sizeof(use));
	
	q.push(start);
	use[start] = true;
	cnt = 1;
	while(!q.empty()) {	
		now = q.front();
		q.pop();
		
		for(int j = 0; j < n; j++) {
			if(enable[now][j] == true && use[j] == false) {
				use[j] = true;
				q.push(j);
				cnt++;
			}
		}
	}

	return cnt;
}

void solve() {
	int result;
	
	// 각 도달 가능 여부 초기화
	memset(enable, 0, sizeof(enable));
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(i == j) {
				enable[i][j] = true;
				continue;
			}
			if((graph[i].p * graph[i].p) >= distance(graph[i].x, graph[i].y, graph[j].x, graph[j].y)) {
				enable[i][j] = true;
			}
		}
	}

	result = -1;
	for(int i = 0 ; i < n; i++) {
		result = max(result, bfs(i));
	}
	
	cout << result << endl;
}

• https://www.acmicpc.net/problem/14172
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.