백준 20005 (보스몬스터 전리품) - java

https://www.acmicpc.net/problem/20005

20005번: 보스몬스터 전리품

 

문제

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

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

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

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

 

유형 : BFS

 

접근 방식

• 플레이어의 수가 최대 26이기 때문에 모두 탐색하는 것은 비효율적이다.
• 문제를 보면 '한 지점에 여러명의 플레이어가 위치'라는 조건이 있기 때문에 보스몬스터를 중심으로 플레이어까지의 거리를 탐색 가능하다.
  • 플레이어를 통과 가능한 지점이라 생각할 경우 맘 편하다 -> 1번의 BFS로 모든 플레이어까지의 거리 계산
• 플레이어의 거리를 구한 경우 시뮬레이션을 돌리면 된다.
• 큐를 사용하였는데 각 플레이어의 정보(이름,거리) 를 큐에 추가하고 매 초가 지날 때마다 거리를 1씩 줄인다.
  • 거리가 0이 된경우 totalDamage에 추가하고 result에도 값을 1 추가한다. 
  • 모든 플레이어를 1칸 이동시켰다면 때린다.

전체 코드

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

public class Main {
    static int n = 0;

    static int m = 0;

    static int k = 0;

    static char[][] board;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    static int[] playerDps = new int[27];

    static int sx = 0;
    static int sy = 0;

    static int[] dis = new int[27];
    static int bossHealth;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        board = new char[n][m];

        for(int i = 0 ; i < n ; i++){

            String line = br.readLine();

            for(int j = 0 ; j < m ; j++){
                board[i][j] = line.charAt(j);

                if(board[i][j] == 'B'){
                    sx = i;
                    sy = j;
                }
            }
        }

        for(int i = 1 ; i <= k ; i++){
            st = new StringTokenizer(br.readLine()," ");

            char playerName = st.nextToken().charAt(0);
            int damage = Integer.parseInt(st.nextToken());

            playerDps[playerName - 'a'] = damage;
        }

        st = new StringTokenizer(br.readLine()," ");
        bossHealth = Integer.parseInt(st.nextToken());

        bfs();
        game();
        br.close();
    }

    static void game(){
        Queue<Point> q = new LinkedList<>();

        for(int i = 0 ; i < 26 ; i++){
            if(playerDps[i] > 0){
                q.add(new Point((char)('a' + i), dis[i]));
            }
        }

        int totalDps = 0;
        int result = 0;

        while(bossHealth > 0){
            int size = q.size();

            while(size > 0){
                size--;
                Point cur = q.poll();

                if(cur.dis - 1  ==  0){
                    totalDps += playerDps[cur.name - 'a']; // 해당 플레이어가 보스에 도착한 경우
                    result += 1;
                }else{
                    q.add(new Point(cur.name,cur.dis - 1)); // 플레이어의 거리를 1 감소
                }
            }

            bossHealth -= totalDps;

        }

        System.out.println(result);
    }

    static void bfs(){
        Queue<Node> q = new LinkedList<>();
        boolean[][] v = new boolean[n][m];
        q.add(new Node(sx,sy,0)); // 보스몬스터의 위치가 시작점
        v[sx][sy] = true;


        while(!q.isEmpty()){
            Node cur = q.poll();

            for(int i = 0; i < 4 ; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue; // 격자를 넘어간 경우

                if(board[nx][ny] == 'X' || v[nx][ny])
                    continue; // 벽이나 이미 방문한 곳

                v[nx][ny] = true;
                q.add(new Node(nx,ny,cur.c + 1));

                if(board[nx][ny] >= 'a' && board[nx][ny] <= 'z'){
                    dis[board[nx][ny] - 'a'] = cur.c + 1; // 플레이어를 찾은 경우 거리 추가
                }
            }
        }


    }
}
class Point{
    char name;
    int dis;

    Point(char name,int dis){
        this.name = name;
        this.dis = dis;
    }
}
class Node{
    int x;
    int y;
    int c;

    Node(int x,int y,int c){
        this.x = x;
        this.y = y;
        this.c = c;
    }
}