[USACO] Moocast

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

---

잘못된 부분을 발견하시면, 댓글 남겨주시면 매우 감사하겠습니다.

문제 상황을 그래프 형태로 만들고, dfs나 bfs로 탐색하면 되는 문제였습니다.

문제에서 소들은 서로 Walkie-Talkie로 소통을 하는데, 소1이 소2에게 메시지를 전송하려면 소1이 가진 Walkie-Talkie의 전력 P가 소2와의 거리보다 크거나 같아야 합니다.
1) 메시지 전송 가능 여부는 거리가 같더라도 각각의 소가 가진 Walkie-Talkie의 전력에 따라 다르기 때문에 소1은 소2에게 메시지를 전송할 수 있는 상황에서, 소2는 소1에게 메시지를 전송하지 못하는 상황도 가능합니다.
2) 또한, 메시지를 직접 전송하지 않고 소1 -> 소2 -> 소3 이런식으로 다른 소를 거쳐 전송하는 것도 가능합니다.
이런 상황에서 한 마리의 소가 메시지를 전송할 때, 최대 몇 마리의 소가 메시지를 받을 수 있는지 찾는 문제였습니다.

1)과 2)의 상황을 종합해서 생각하면, 그래프는 단방향 그래프로 표현할 수 있고, 가능한 모든 소의 쌍을 확인하면서 메시지 전송이 가능한 쪽으로 소들을 이어주면 된다는 것을 알 수 있습니다. 이후에는 그래프의 연결 요소를 탐색하면서 각 연결 요소가 가진 노드 개수의 최댓값을 찾으면 됩니다.

---

import java.io.*;
import java.util.*;

public class Main {

    static int n, cnt;
    static List<Integer>[] adj = new List[200];
    static boolean[] vis;

    private static void dfs(int cur){
        vis[cur] = true;
        for(int nxt : adj[cur]){
            if(vis[nxt]) continue;
            cnt++;
            dfs(nxt);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(bf.readLine());
        int[] x = new int[n], y = new int[n], p = new int[n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<n; i++) adj[i] = new ArrayList<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int dist = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
                if(dist <= p[i] * p[i]) adj[i].add(j);
            }
        }

        int ans = Integer.MIN_VALUE;
        for(int i=0; i<n; i++){
            cnt = 1; vis = new boolean[200];
            dfs(i);
            ans = Math.max(ans, cnt);
        }

        System.out.println(ans);
    }
}

시간 복잡도는 O(N^2)입니다.