[BOJ14172] Moocast

문제

• 소 N(1<= <=200)마리가 응급상황을 대비해 moocast 구축
• 2차원 지도상에서 P 파워(도달거리)로 전송
• A 소가 B소한테 바로 전송할 수 있지만, 반대는 아닌 경우도 있음(파워 약해서)
• Relay 전송이 가능
• 한 소에서 전달 가능한 모든 소의 수의 최대값

입력

• N
• N 줄에 x y p (x,y : 좌표, p : 파워)

출력

• 한 소가 전달할 수 있는 최대의 소의 수

설계

• 특정 소가 다른 소한테 도달할 수 있는 그래프 구현
• p값을 기준으로 거리를 측정해 경로 구현
• 경로를 기반으로 dfs를 이용한 단순 깊이 최대를 짰는데, 계속 틀렸음
• 단순 깊이가 아니라, 하나의 시작점에서 뻗어나갈 수 있는 최대 노드의 수였음
• Dfs 썼다가 bfs로도 짜보고 별 짓을 다 해서, 그냥 bfs로 마무리 했음
• while(!queue.empty) 반복문을 도는 수를 체크하여 maximum 구하기

How I solved(click to github)

---

ref :
BOJ14172