[Java] 백준 20005. 보스몬스터 전리품

문제 링크 - https://www.acmicpc.net/problem/20005

 

 

---

 

 

 

 

 

문제

멤멤월드에서는 일정 주기마다 랜덤한 위치에서 보스몬스터가 소환된다.

이 보스몬스터의 전리품은 아주 좋아 모든 멤멤월드의 플레이어들은 소환 알림만을 기다린다고 한다. 전리품은 한 대라도 때렸다면 피해를 준 비율대로 지급된다고 한다.

현재 멤멤월드의 지도와 플레이어들의 정보, 보스몬스터의 체력이 주어졌을 때 최대 몇 명의 플레이어가 전리품을 가져갈 수 있는지 계산해보자.

단, 모든 플레이어는 보스몬스터가 소환되면 보스몬스터의 위치로 최대한 빠른 경로로 이동하며 이동한 경우 공격을 바로 시작한다. 공격에 소모되는 시간은 1초이며 보스와 같은 위치에 있는 모든 플레이어의 공격은 동시에 이뤄진다. 그리고 플레이어는 상, 하, 좌, 우로 이동할 수 있고 이동에 소요되는 시간은 1초이다. 또한 한 지점에 여러명의 플레이어가 위치할 수 있다.

 

 

입력

입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다.

입력의 둘째 줄부터 M개의 줄까지 지도의 정보가 주어진다. 이때 ‘.’은 이동할 수 있는 길, ‘X’는 이동할 수 없는길, 알파벳 소문자는 플레이어의 아이디이며 ‘B’는 보스몬스터의 위치이다.

그 다음 줄부터 P개의 줄까지 플레이어의 아이디와 dps(1 ≤ dps ≤ 10000)가 주어진다. 아이디는 영문 소문자이다. dps란 1초당 얼만큼의 보스몬스터의 체력을 줄일 수 있는지 의미한다. 그 다음 줄은 보스몬스터의 HP(10 ≤ HP ≤ 1000000)가 주어진다. dps와 HP는 정수이다.

아무 플레이어도 보스몬스터를 잡으러 갈 수 없는 경우의 입력은 주어지지 않는다.

 

 

출력

전리품을 가져갈 수 있는 플레이어의 수의 최댓값을 출력한다.

 

 

 

 

 

 

 

---

 

풀이

BFS로 풀면 된다. 플레이어들이 아닌 보스를 큐에 넣고 플레이어들의 위치를 탐색한다.

물론 플레이어들을 큐에 넣고 보스의 위치를 탐색하는 방법도 가능하지만, 보스는 단 하나의 위치만 존재하는 반면 플레이어는 최대 26명까지 존재할 수 있다.

보스를 큐에 넣고 탐색할 경우 O(N x M)으로 각 플레이어들과의 최단 거리를 한 번에 계산할 수 있다.

반면 각 플레이어들을 큐에 넣고 탐색할 경우, 최대 26번의 BFS를 수행해야 하므로 O(P x N x M)으로 탐색 시간이 증가하게 된다. 

 

보스를 큐에 넣고 탐색 : O(N x M)

플레이어를 넣고 탐색  : O(P x N x M)

 

따라서 보스를 큐에 넣고 탐색하는 방식이 더 효율적이다.

 

• 보스를 큐에 넣고 각 플레이어들을 탐색하며 탐색 중 플레이어를 만날 경우 전리품 대상 플레이어 수(totalCount)를 증가해 주고, 동시에 보스를 공격할 수 있는 총 공격력(totalPower)을 증가시켜준다.
• 1초가 지날 때마다 보스의 체력을 플레이어들의 공격력(totalPower) 만큼 감소시킨다. 

 

이 과정을 보스의 체력이 0이 될 때까지 반복하면 된다.

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/20005
public class Main {
    private static final char WALL = 'X', BOSS = 'B', EMPTY = '.';
    private static int N, M, HP;
    private static int bossR, bossC;
    private static char[][] map;
    private static int[] power;


    public static void main(String[] args) throws IOException {
        init();

        int playerCnt = getPlayerCount();
        System.out.print(playerCnt);
    }//main


    private static int getPlayerCount() {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        int totalCount = 0; // 전리품을 가져갈 수 있는 플레이어의 수
        int totalPower = 0; // 플레이어들 파워
        int prevTime = 0; // 이전 시간

        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];

        q.offer(new int[] {bossR, bossC, 0});
        visited[bossR][bossC] = true;

        int r, c, time, player;

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            r = cur[0]; // 행
            c = cur[1]; // 열
            time = cur[2]; // 시간

            if(time != prevTime) {
            	// 모든 플레이어의 공격은 동시에 이뤄진다.
                HP -= totalPower;
                prevTime = time;

                if(HP <= 0) break;
            }

            if(map[r][c] != EMPTY) {
                player = map[r][c] - 'a';
                totalCount++; // 전리품을 가져갈 수 있는 플레이어 수 증가
                totalPower += power[player]; // 공격 파워 증가
            }

            for(int i=0; i<4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(rangeCheck(nr, nc) || visited[nr][nc]) continue;

                visited[nr][nc] = true;
                q.offer(new int[] {nr, nc, time+1});
            }
        }

        return totalCount;
    }//getPlayerCount


    private static boolean rangeCheck(int r, int c) {
        return r < 0 || r >= N || c < 0 || c >= M || map[r][c] == WALL;
    }//rangeCheck


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 지도의 크기를 나타내는 두 정수 M, N과 플레이어의 수 P가 주어진다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        power = new int[P];
        map = new char[N][M];


        // 지도의 정보가 주어진다.
        boolean flag = true;
        for(int i=0; i<N; i++) {
            map[i] = br.readLine().toCharArray();
            for(int j=0; j<M && flag; j++) {
                if(map[i][j] == BOSS) { // 보스
                    map[i][j] = EMPTY;
                    bossR = i;
                    bossC = j;
                    flag = false;

                    break;
                }
            }
        }

        // 플레이어의 아이디와 dps(1 ≤ dps ≤ 10000)가 주어진다.
        for(int i=0; i<P; i++) {
            st = new StringTokenizer(br.readLine());
            int player = st.nextToken().charAt(0) - 'a';
            int dps = Integer.parseInt(st.nextToken());
            power[player] = dps;
        }

        // 보스몬스터의 HP(10 ≤ HP ≤ 1000000)가 주어진다.
        HP = Integer.parseInt(br.readLine());

        br.close();
    }//init


}//class