[solved.ac 골드4] 1430_공격 (파이썬, BFS)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

다솜이는 누구나 쉽게 게임을 만들 수 있도록 하기 위해 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)까지 허용한다.

예제

힌트

예제 1: 탑4 -> 탑3 10 전송 탑3 -> 탑2 15 전송 탑2 -> 탑1 17.5 전송 탑1 -> 적 18.75 공격

---

나의 풀이

허접한 그림을 그려봤다.

적을 공격할 수 있는 탑은 거리가 R 이내에 있는 탑만 가능하다. 그 밖에 있는 청록색 탑은 적을 직접 공격할 수 없다.

적에게 최대 피해를 주기 위해서는 직접 적을 공격할 수 없는 탑들이 에너지를 넘겨주어야 하는데 에너지를 어떤 탑에게 어떻게 전달해주어야 가장 효과적일까?

에너지 전달

현재 적에게 직접 공격할 수 있는 탑1, 탑2가 있고, 탑1, 2에 에너지를 줄 수 있는 거리에 탑3가 있다. 이때 초기에 모든 탑이 E 만큼의 에너지를 가지고 있다고 했을 때 탑3가 탑1과 탑2에 각각 에너지를 줄 수가 있다.

각각 x, y 만큼 에너지를 준다고 하면 반토막이 나면서 x/2, y/2 만큼 받을 수 있게 된다.

이 상황에서는 적은 2E + x/2 + y/2 만큼의 피해를 받게 된다.

---

이번에는 탑1, 2에 각각 에너지를 주는 것이 아니라 하나의 탑에 몰빵하는 경우를 살펴보자.

탑3이 E(x+y) 만큼의 에너지를 소모해서 (x+y)/2 만큼의 에너지를 탑1에게 준 경우 적이 받게 되는 피해는 2E + (x+y)/2 만큼이 된다.

결국 에너지를 쪼개서 주나, 한 쪽에 몰빵해주나 적이 받게 되는 피해는 똑같다.

그래프(트리)로 표현

적과 탑 간의 관계는 위 그림과 같이 트리 형태로 만들 수 있다.

부모 노드와 자식 노드는 서로 거리가 R 보다 작거나 같은 경우 연결될 수 있다.

루트 노드는 적이 된다.

(루트 노드를 제외하고) 부모 노드는 여러 자식 노드를 가질 수 있으며, 이는 부모 노드(탑)에 에너지를 줄 수 있는 탑이 여러 개 존재할 수 있다는 의미이다.

반대로 자식 노드는 여러 부모가 있을 수 없다. 위에서 에너지를 나눠주나 하나에 몰빵해주나 결국 똑같다는 것을 보였기 때문에 하나의 탑에 몰빵해주는 경우만 고려하면 된다.

각각 타워는 초기에 E 만큼의 에너지를 가지고 있다.

그럼 최종적으로 적에게 입힐 수 있는 피해는 각각 어느 정도일까?

각 Depth 별로 하나씩만 그려보았다.

적에게 직접 공격할 수 있는 탑은 E 만큼의 피해를 직접 입힐 수 있다.

2번째 Depth의 탑은 E의 절반 만큼을 부모 탑에게 줄 수 있으므로 결국 E/2 만큼 적에게 피해를 입힐 수 있다.

3번째 Depth의 탑은 E의 절반의 절반 만큼의 피해를 입힐 수 있다.

결론

적을 루트 노드로 하는 트리 구조를 만든 후 Depth를 고려하여 각 타워가 입힐 수 있는 피해의 합을 구하면 적이 받는 최대 피해를 구할 수 있다.

---

전체 코드

from collections import deque

n, r, e, ex, ey = map(int, input().split())
tops = {tuple(map(int, input().split())) for _ in range(n)}
answer = 0

def bfs(x, y):
    global answer, tops

    q = deque([(x, y, 0)])

    while q:
        x, y, depth = q.popleft()
        if depth:
            answer += e / (2 ** (depth - 1))

        # 거리 내에 있는 탑 찾기
        candidate = []
        for top in tops:
            if (x - top[0]) ** 2 + (y - top[1]) ** 2 <= r ** 2:
                candidate.append(top)
        # 탑 추가
        for top in candidate:
            q.append((top[0], top[1], depth + 1))
        # 탑 제거
        tops -= set(candidate)

bfs(ex, ey)
print(round(answer, 2)) if int(answer) != answer else print(f'{answer}.0')

q에서 꺼내서 e / 2 ^ (depth - 1) 을 answer에 더하는 부분이 각 Depth를 고려하여 적에게 최종적으로 입힐 수 있는 피해를 더하는 부분이다.

거리 내에 있는 탑을 찾기 위해서는 두 좌표 사이의 거리 구하는 공식을 이용했다.

두 좌표 사이의 거리

 

탑들은 Set으로 관리했다. 문제에서 위치가 겹치는 탑이 존재하지 않는다고 했고, 이미 방문한 탑을 제거하기에도 리스트보다 더 효율적이다. 그리고 탑 간의 순서가 중요하지 않았기 때문에 Set이 적합하다.

출력에서 주의해야 할 점이 round(answer, 2)를 하면 소수점 아래 2자리까지 구할 수 있지만 answer이 정수인 경우 소수점이 표시되지 않는다. (예를 들어 answer이 2라면 2.0 이 아닌 2로 출력된다.)

예제 5에서 0을 출력할 때 0.0을 출력하도록 했기 때문에 정수인지 판별 후 정수라면 뒤에 ".0" 을 붙여서 출력해주었다.

채점 결과