[알고리즘/백준] 1430번 공격 Python 파이썬

 

이번 문제는 처음에는 헷갈렸지만 후반에 생각을 바꿔서 수월하게 풀렸다.

 

 

적이 총 받는 최대 에너지를 구하는 문제로 거리 계산과 경우 수를 잘 따져봐야하는 문제이다. 먼저 문제 읽고 나서 생각해보니 한 탑에 몰아서 주든 나눠서 주든 딱히 값의 차이가 없다는 것을 인지했다. 그리고 처음에는 해당 로직을 적 주변에 있는 탑을 검사해서 해당 탑으로부터 주변 탑들을 탐색해가는 DFS 를 활용한 방법으로 풀었다. 하지만, 이 경우 적 주변 탑이 여러개 인 경우 처음 탑을 기준으로 주변 탑을 먼저 찾게 되는데 이 과정에서 다른 적 주변 탑으로 직통할 수 있는 탑이 경유하게 되어 최대 에너지를 구하지 못하는 문제가 발생하였다. 

 

이를 해결하기 위해 DFS가 BFS 를 활용해서 적을 기준으로 주변 탑을 검사해서 넣어주는 작업을 진행하였다. 이 경우에는 위의 같은 문제를 방지할 수 있게 된다.

 

다음과 같은 코드로 통과하였다.

 

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

n, r, d, x, y = map(int, input().split())
top_list = []
have_en = []
attack_top_list = []
answer_count = 0

for i in range(n):
    tx, ty = map(int, input().split())
    top_list.append([tx, ty])
    have_en.append(True)

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

def bfs(x, y, d):
    global answer_count
    q = deque([(x, y, d)])

    while q:
        cx, cy, e = q.popleft()
        for i in range(n):
            if have_en[i] == True and distance(cx, cy, top_list[i][0], top_list[i][1]) <= r:
                answer_count += e
                have_en[i] = False
                q.append((top_list[i][0], top_list[i][1], e/2))

bfs(x, y, d)
print(answer_count)

 

개인적으로 BFS보다 DFS를 선호해서 이런 문제들을 DFS로 풀려고 하는데 아무래도 둘 다 쓰임새가 다르고 각 맞는 문제가 존재하다 보니 처음부터 두 방법을 고려해서 푸는 게 맞는 거 같다.