[Python/BOJ] 1430. 공격

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

1430번: 공격

문제

다솜이는 누구나 쉽게 게임을 만들 수 있도록 하기 위해 Microsoft에서 출시한 XNA Game Studio Express를 가지고 게임을 만들었다.

다솜이의 게임은 적의 공격에 대비해서 도시를 방어하는 게임이다. 도시에는 탑이 N개가 있다. 각각의 탑은 X-Y좌표 평면위에 존재한다. 또, 탑은 맨 처음에 D의 에너지를 가지고 있고, 탑의 사정거리는 R이다.

탑 주변에 적이 나타나면, 탑은 적을 다음과 같은 방법으로 공격할 수 있다.

일단, 탑은 자신의 에너지를 재분배할 수 있다. 만약 서로 다른 두 탑의 거리가 R보다 작거나 같다면, 둘 중에 한 탑은 다른 탑에게 에너지를 자기가 가지고 있는 한도내에서 자유롭게 전송할 수 있다. 하지만, 에너지를 전송할 때는, 절반을 잃는다. (탑 1이 탑 2에게 에너지를 10 전송하면, 탑 1은 에너지를 10을 잃고, 탑 2는 에너지를 5 얻는다.)

탑이 적을 공격할 때는, 적과 탑의 거리가 R보다 작거나 같아야한다. 탑에서 적을 공격할 때는, 자신의 모든 에너지를 적을 공격하는데 쓴다. 이때 적이 받는 데미지는 에너지의 양과 같다.

적이 받을 수 있는 에너지의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 탑의 개수 N, 사정 거리 R, 초기 에너지 D, 적의 X좌표 X, 적의 Y좌표 Y가 주어진다. 둘째 줄부터는 탑의 위치가 한 줄에 하나씩 X좌표 Y좌표 순으로 주어진다. N은 50보다 작거나 같은 자연수이고, R은 500보다 작거나 같은 자연수, D는 100보다 작거나 같은 자연수이다. 모든 X좌표와 Y좌표는 1,000보다 작거나 같은 음이 아닌 정수이다. 탑의 위치가 같은 경우는 없고, 적과 탑의 위치가 같은 경우도 입력으로 주어지지 않는다.

출력

첫째 줄에 적이 받는 데미지의 최댓값을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

풀이

Code

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

def solution(n, r, d, x, y, information):
    # 1. 배수 변수 생성
    multiple = 0
    # 2. 방문 여부 비트 생성
    visited = 0
    # 3. 큐 생성
    queue = deque()
    # 4.
    for idx, info in enumerate(information) :
        nx, ny = info
        # 4-1. 적과의 사정 거리 안에 들 경우
        if r ** 2 >= (nx - x) ** 2 + (ny - y) ** 2 :
            # 큐에 좌표 삽입
            queue.append((nx, ny, 1))
            # 방문 처리
            visited |= ( 1 << idx )
            # 배수 업데이트
            multiple += 1
    # 5.
    while queue :
        # 5-1. 좌표 인덱스 반환
        a, b, m = queue.popleft()
        m /= 2
        # 5-2.
        for idx, info in enumerate(information) :
            nx, ny = info
            # 5-2-1. 방문한 적이 없으며 현재 탑과 에너지를 주고받을 수 있는 경우
            if not visited & ( 1 << idx ) and  r ** 2 >= (nx - a) ** 2 + (ny - b) ** 2 :
                # 배수 업데이트
                multiple += m
                # 방문 처리
                visited |= ( 1 << idx )
                # 큐에 다음 포탑 위치 삽입
                queue.append((nx, ny, m))
    # 6. 결과 출력
    print(round(d * multiple, 3))

if __name__ == "__main__" :
    n, r, d, x, y = map(int, input().split())
    information = [list(map(int, input().split())) for _ in range(n)]
    solution(n, r, d, x, y, information)