백준 #1430 공격

코드

import sys, math
# sys.stdin = open("input.txt")
from collections import deque
input = sys.stdin.readline


def get_distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def solve(start):
    global answer
    q = deque()
    q.append((start, d))
    visited = [False] * n
    visited[start] = True
    while q:
        cur, power = q.popleft()
        if graph[cur][0] <= r:
            answer += power
            return
        for nxt in range(n):
            if get_distance(graph[nxt][1], graph[nxt][2], graph[cur][1], graph[cur][2]) <= r:
                if not visited[nxt]:
                    q.append((nxt, power / 2))
                    visited[nxt] = True


n, r, d, x, y = map(int, input().split())
graph = []

for _ in range(n):
    _x, _y = map(int, input().split())
    graph.append([get_distance(_x, _y, x, y), _x, _y, d])

graph.sort()
answer = 0
for i in range(n):
    solve(i)

print(answer)

풀이

각 타워로부터 적까지 도달하면서 최대 몇 데미지를 입힐 수 있는지 계산하여 출력

bfs를 이용했는데 적으로부터 가까운 순으로 정렬해서 bfs안의 for 문을 전체를 돌지 말고

자기 자신 전까지만 방문하면서 구하려 했었는데 실패했었다(거리 순으로 정렬 했기 때문에 가능 하다고 생각 했음)

왜 안되는지 좀 더 생각!