BOJ 20005 - 보스몬스터 전리품

문제

백준 온라인 저지 - 20005번

풀이 과정

해당 문제는 pypy3로 풀이했습니다.

몬스터와 플레이어의 위치가 주어질 때 몬스터를 처치해서 보상을 얻을 수 있는 플레이어의 수를 구하는 문제입니다.

플레이어는 몬스터에게 최단 거리로 이동하기 때문에 BFS 를 이용해서 몬스터 까지의 최단 경로룰 구하면 됩니다.
이때 상태공간 S 는 다음과 같이 정의할 수 있습니다.

S[x][y][player] = (x, y) 지점에 player 가 이미 방문한 적이 있는지 유무

한 가지 실수를 했던 점은 `BFS` 가 종료되기 위한 조건으로 `queue` 가 비어있는지를 체크한 것인데,
사실 더 이상 이동할 곳이 없더라도 몬스터의 체력이 0 이하가 될 때까지 게임을 진행해야해서 계속 틀렸었습니다.
따라서 이 부분만 유의해서 문제를 풀면 될 것 같습니다.

코드

import sys
from collections import deque
from functools import reduce


M, N, P = list(map(int, sys.stdin.readline().split()))
board = [list(sys.stdin.readline().strip()) for _ in range(M)]
powers = {}
player_indices = {}
for idx in range(P):
    player, power = list(sys.stdin.readline().split())
    powers[player] = int(power)
    player_indices[player] = idx
HP = int(input())

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def pre_processing(board):
    positions = []

    for x in range(M):
        for y in range(N):
            if 'a' <= board[x][y] <= 'z':
                positions.append([x, y, board[x][y]])

    return positions


def bfs(positions):
    global HP

    q = deque()
    visit = [[[0] * P for _ in range(N)] for _ in range(M)]
    arrived = []

    for x, y, player in positions:
        q.append([x, y, player])
        visit[x][y][player_indices[player]] = 1

    while HP > 0:
        loop = len(q)

        for _ in range(loop):
            x, y, player = q.popleft()
            player_idx = player_indices[player]

            if board[x][y] == 'B':
                arrived.append(player)
                continue

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

                if 0 <= nx < M and 0 <= ny < N:
                    if board[nx][ny] != 'X' and not visit[nx][ny][player_idx]:
                        q.append([nx, ny, player])
                        visit[nx][ny][player_idx] = 1

        # 몬스터 공격
        if len(arrived):
            HP -= reduce(lambda acc, p: acc + powers[p], arrived, 0)

    return len(arrived)


def solution():
    positions = pre_processing(board)
    answer = bfs(positions)

    return answer


print(solution())