Moocast

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

14172번: Moocast

 

소들이 메시지 전달할 수 있는지는 O(N^2)으로 모두 조사합니다.

문제에도 나와있지만, 한 가지만 주의하면 됩니다.

 

(A -> B로 갈 수 있다) != (B - > A로 갈 수 있다)

두 소의 워키토키의 power에 따라 메시지를 보낼 수 있는지를 조사해봐야 합니다.

 

모두 조사를 한 다음, 모든 소들을 시작점으로 하여 BFS를 돌려봅니다.

최대값이 나오면 ans 값을 갱신해 줍니다.

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <queue>
 
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
int n;
struct tt{
    int y, x, power;
};
vector<tt> v;
vector<int> vv[201];
 
int main() {
    FastIO;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        for (int j = 0; j < v.size(); j++) {
            int xx = abs(v[j].y - a), yy = abs(v[j].x - b);
            double dist = sqrt(xx*xx + yy * yy);
            if (dist <= (double)c) vv[i].push_back(j);
            if (dist <= (double)v[j].power) vv[j].push_back(i);
        }
 
        v.push_back({ a,b,c });
    }
 
    int ans = 0;
    for (int s = 0; s < n; s++) {
        bool chk[201] = {};
        int cnt = 1;
        queue<int> q;
        q.push(s);
        chk[s] = true;
        while (!q.empty()) {
            int f = q.front();
            q.pop();
            for (int i = 0; i < vv[f].size(); i++) {
                int next = vv[f][i];
                if (chk[next]) continue;
                chk[next] = true;
                q.push(next);
                cnt += 1;
            }
        }
        ans = max(ans, cnt);
    }
 
 
    cout << ans;
}