[정올 5394] 무전기 - JAVA

문제 링크

문제 정의

• $N$명의 병사, 각각 무전기 보급 받음
• 각 무전기의 성능 차이가 존재: 통신 가능 거리 = $P$
• 한 명의 병사가 다른 병사에 명령을 전달 받으면 해당 병사가 다른 병사들에게 전달 가능
• 병사 $A$가 병사 $B$에게 통신이 가능해도 역은 항상 성립하지 않는다.

한 명의 병사를 뽑아 다른 병사들에게 최대한 정보를 전달할 수 있는 최대 병사의 수를 구해라

---

접근 방법

1. 그래프 탐색 문제로 접근

가장 핵심 조건은 세 번째 조건입니다.
시작 병사로부터 다른 통신병을 거쳐 전달이 가능하다는 조건으로 해당 문제를 어떤 방식으로 해결할 수 있는 문제인지 파악하기 가장 좋은 조건입니다.

각 병사마다 전달할 수 있는 병사들을 인접 리스트 형식으로 정리한다면 그래프 탐색으로 문제를 해결할 수 있다고 생각했습니다.

2. 무방향 그래프, 방향 그래프

그래서 "통신 가능하다"의 정의를 어떻게 해야할지에 따라
무방향 그래프가 될 수 있고 방향 그래프도 될 수 있습니다.

이것을 알 수 있게 하는 조건은 네 번째 조건입니다

"병사 $A$가 병사 $B$에게 통신이 가능해도 역은 항상 성립하지 않는다."

즉,
병사 $A$가 병사 $B$에게 통신 가능하더라도
병사 $B$가 병사 $A$에게 통신 가능하다는 것을 보장하지 않는다.

각각 체킹해야 한다는 것을 의미하므로 방향 그래프 문제로 정의했습니다.

3. 시작 지점이 존재하지 않음

이 문제에서 걱정 되었던 것은
통신을 시작하는 사람이 정해지지 않았기 때문에
완전 탐색을 수행하면서 발생하는 TLE가 걱정되었습니다.

하지만 $N$의 범위가 200이였기 때문에
"병사들 모두 탐색 로직을 수행해서 최댓값을 구하자" 라고 생각하고 문제를 풀게 되었습니다.

4. 탐색 로직

문제를 해결하기 위해서는 인접 리스트를 구하고
각 병사마다 탐색을 수행해서 정보를 전달받는 병사의 수가 최대가 되게하는 값을 구해야 했고 탐색 로직은 DFS로 구현했습니다.

---

코드

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

class Node {
	int x;
	int y;
	int p;
	
	public Node (int x, int y, int p) {
		this.x = x;
		this.y = y;
		this.p = p;
	}
}

class Edge {
	int v;
	Edge edge;
	
	public Edge (int v, Edge edge) {
		this.v = v;
		this.edge = edge;
	}
}

public class Main {
	static StringTokenizer st;
	static Node[] node;
	static Edge[] graph; 
	static int answer;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine().trim());
		node = new Node[N];
		graph = new Edge[N];
		
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());
			
			node[i] = new Node(x, y, P);
		}
		
		
		for (int u = 0; u < N; u++) {
			for (int v = u+1; v < N; v++) {
				if (u == v) continue;
				
				if (checkInbound(u, v)) {
					graph[u] = new Edge(v, graph[u]);
				}
				
				if (checkInbound(v, u)) {
					graph[v] = new Edge(u, graph[v]);
				}
			}
		}
		
		answer = 0;
		for (int i = 0; i < N; i++) {
			answer = Math.max(answer, dfs(i, new boolean[N]));
		}
		
		System.out.println(answer);
		
	}
	
	static boolean checkInbound(int i, int j) {
		int absX = Math.abs(node[i].x - node[j].x);
		int absY = Math.abs(node[i].y - node[j].y);
		
		double cal = Math.sqrt(Math.pow(absX, 2) + Math.pow(absY, 2));
		
		return node[i].p >= cal;
	}
	
	
	static int dfs(int v, boolean[] visited) {
		if (visited[v]) return 0;
		visited[v] = true;
		
		int count = 1;
		
		for (Edge edge = graph[v]; edge != null; edge = edge.edge) {
			int nv = edge.v;
			count += dfs(nv, visited);
		}
		
		return count;
	}
}