이번 문제는 BFS와 딕셔너리를 활용하여 해결하였다. 각 플레이어들의 위치를 저장하고, 각 플레이어 별로 BFS를 통해 보스의 위치까지 이동하는 데에 걸리는 시간을 딕셔너리에 저장하였다. 이 결과 만들어지는 걸리는 시간 리스트를 활용하여 보스의 체력이 떨어질 때까지 반복하며 관여하는 플레이어를 set에 담아 set의 길이를 출력하여 해결하였다.

Code

from collections import defaultdict, deque
m, n, p = map(int, input().split())
grid = [list(str(input())) for _ in range(m)]
location = defaultdict(tuple)
powers = defaultdict(int)
for i in range(m):
    for j in range(n):
        if grid[i][j] != 'B' and grid[i][j] != '.' and grid[i][j] != 'X':
            location[grid[i][j]] = (i, j)
for _ in range(p):
    a, b = map(str, input().split())
    powers[a] = int(b)
boss = int(input())
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
arrived_time = defaultdict(int)
def kill_boss(player):
    q = deque()
    py, px = location[player]
    q.append((py, px, 0))
    visited = [[False for _ in range(n)] for _ in range(m)]
    visited[py][px] = True
    while q:
        y, x, time = q.popleft()
        if grid[y][x] == 'B':
            arrived_time[player] = time
            break
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < m and 0 <= nx < n and grid[ny][nx] != 'X' and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx, time+1))
for key, _ in location.items():
    kill_boss(key)
cnt = set()
time = 0
while boss:
    for key, value in arrived_time.items():
        if value <= time:
            if key not in cnt:
                cnt.add(key)
            boss = max(0, boss-powers[key])
    time += 1
print(len(cnt))