[BOJ] 공격 - 1430 (G4)

시간 제한	메모리 제한
2 초	128 MB

문제

기지에서 출발하여 반경 R 이내에 있는 모든 타워를 공격한다. 타워를 공격하면 그 타워로부터 다시 반경 R 이내의 다른 타워를 공격할 수 있다. 각 단계마다 공격력은 반감된다.

최대 공격력을 구하는 프로그램을 작성하시오.

풀이

BFS를 사용하여 거리 내의 타워를 탐색하고, 각 단계마다 공격력을 반감시킨다.

코드

import sys
from collections import deque
input = sys.stdin.readline

def distance(x1, y1, x2, y2, r_squared):
    dist_sq = (x2 - x1) ** 2 + (y2 - y1) ** 2
    return dist_sq <= r_squared

def solve():

    N, R, D, X, Y = map(int, input().split())

    graph = [[0, 0]]
    for _ in range(N):
        graph.append(list(map(float, input().split())))

    v = [False] * (N + 1)
    
    q = deque([(X, Y, 0)])
    
    result = 0.0
    
    r_sq = R * R

    while q:
        cur_x, cur_y, count = q.popleft()

        for i in range(1, N + 1):
            target_x, target_y = graph[i]

            if not v[i] and distance(cur_x, cur_y, target_x, target_y, r_sq):
                v[i] = True

                result += (D / (2 ** count))
                
                q.append((target_x, target_y, count + 1))

    print(result)
solve()

시간 복잡도

O(N^2)