백준 20005 보스몬스터 전리품

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/20005

풀이

난이도 : Gold III

이 문제는 어렵다기보다는 구현하기에 복잡하여 시간이 조금 걸린 문제였다.
처음 입력을 받을 배열 array, player들의 좌표를 저장할 players, player들의 공격력을 저장할 attack, 각각의 player들과 보스 간의 거리를 저장할 distance을 사용하였다. 같은 player는 같은 index를 갖도록 하였다.

1) bfs를 이용하여 각 player들과 보스 사이의 거리를 구해주었다.
2) 1초를 한 턴이라고 생각하고 한 턴 안에 일어나는 일들은 while문 한번을 돌 때 모두 마무리를 지어 주었다.

• 보스와의 거리를 비교하여 거리가 0이 아니면 거리를 1 좁힌다.
• 거리가 0이고, 처음 접근한다면 정답에 count될 results를 True로 만들어주고, 총 공격력에 해당 플레이어의 공격력을 더해준다.
• 거리가 0이고, 이미 접근한 적이 있다면 넘어간다.
• 모든 플레이어에 대한 일들이 끝나면 보스에게 공격을 한다. (hp를 줄인다.)
• hp가 0이하라면 while문을 종료한다.

👉 이 문제는 입력값 m, n의 순서를 일반적인 문제들과 다르게 거꾸로 받음과 동시에 m을 세로, n을 가로로 두는데, 이 때문에 IndexError가 발생하여 문제를 푸는데 조금 헷갈렸었던 문제이다.

👉 이 문제는 백준에서 python3로 제출하면 시간 초과가 발생하므로, pypy3로 제출해야 한다.

코드

<import sys
from collections import deque

input = sys.stdin.readline

m, n, p = map(int, input().split())
array = []
players = []
attack = []
distance = []
results = [False] * p
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for _ in range(m):
    array.append(list(str(input())))

for i in range(m):
    for j in range(n):
        if array[i][j] != '.' and array[i][j] != 'X' and array[i][j] != 'B':
            players.append([i, j, array[i][j]])

for _ in range(p):
    tmp = list(map(str, input().split()))
    attack.append([tmp[0], int(tmp[1])])

players.sort(key=lambda x: x[2])
attack.sort()

hp = int(input())

def bfs(x, y):
    visited = [[False] * n for _ in range(m)]
    q = deque()
    q.append([x, y, 0])
    visited[x][y] = True

    results = []

    while q:
        x, y, c = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= m or ny >= n:
                continue
            if visited[nx][ny] or array[nx][ny] == 'X':
                continue
            
            if array[nx][ny] == 'B':
                results.append(c+1)
            if len(results) != 0:
                continue

            visited[nx][ny] = True
            q.append([nx, ny, c+1])

    return min(results)

for player in players:
    distance.append(bfs(player[0], player[1]))

all_attack = 0
while hp > 0:
    for i in range(p):
        if distance[i] == 0:
            if results[i]:
                continue
            results[i] = True
            all_attack += attack[i][1]
        else:
            distance[i] -= 1
    
    hp -= all_attack

count = 0
for r in results:
    if r:
        count += 1

print(count)