문제
멤멤월드에서는 일정 주기마다 랜덤한 위치에서 보스몬스터가 소환된다.
이 보스몬스터의 전리품은 아주 좋아 모든 멤멤월드의 플레이어들은 소환 알림만을 기다린다고 한다. 전리품은 한 대라도 때렸다면 피해를 준 비율대로 지급된다고 한다.
현재 멤멤월드의 지도와 플레이어들의 정보, 보스몬스터의 체력이 주어졌을 때 최대 몇 명의 플레이어가 전리품을 가져갈 수 있는지 계산해보자.
단, 모든 플레이어는 보스몬스터가 소환되면 보스몬스터의 위치로 최대한 빠른 경로로 이동하며 이동한 경우 공격을 바로 시작한다. 공격에 소모되는 시간은 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는 정수이다.
아무 플레이어도 보스몬스터를 잡으러 갈 수 없는 경우의 입력은 주어지지 않는다.
출력
전리품을 가져갈 수 있는 플레이어의 수의 최댓값을 출력한다.
예제 입력 1
6 6 3
b.Bc..
......
.a....
......
...X..
.....X
a 36
b 19
c 39
79예제 출력 1
2예제 입력 2
6 6 5
.....B
e...X.
.d....
c.....
....a.
.....b
a 4
b 22
c 29
d 98
e 94
253예제 출력 2
4예제 입력 3
6 6 4
......
...a..
..bBc.
...d..
......
......
a 4
b 4
c 4
d 4
10예제 출력 3
4풀이
이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
static int hp;
static int M;
static int N;
static int P;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
M = Integer.parseInt(input[0]);
N = Integer.parseInt(input[1]);
P = Integer.parseInt(input[2]);
Pair[] players = new Pair[P];
int[] dps = new int[P];
char[][] map = new char[M][N];
for(int i=0; i<M; i++) {
String str = br.readLine();
for(int j=0; j<N; j++) {
map[i][j] = str.charAt(j);
if(map[i][j]>='a' && map[i][j]<='z') {
players[map[i][j]-'a'] = new Pair(i, j, 0, 0);
map[i][j] = '.';
}
}
}
for(int i=0; i<P; i++) {
String[] str = br.readLine().split(" ");
dps[i] = Integer.parseInt(str[1]);
}
hp = Integer.parseInt(br.readLine());
bfs(map, dps, players);
}
public static void bfs(char[][] map, int[] dps, Pair[] players) { //각 플레이어가 보스몬스터에 도착하는 최단 시간
Queue<Pair> queue = new LinkedList<>();
PriorityQueue<Fight> pq = new PriorityQueue<>();
boolean[][] visited;
for(int i=0; i<P; i++) {
Pair p = players[i];
visited = new boolean[M][N];
visited[p.x][p.y] = true;
queue.add(new Pair(p.x, p.y , 0, i));
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(map[temp.x][temp.y]=='B') {
pq.add(new Fight(temp.idx, temp.t));
break;
}
for(int j=0; j<4; j++) {
int nx = temp.x+dx[j];
int ny = temp.y+dy[j];
if(nx<0 || nx>=M || ny<0 || ny>=N || visited[nx][ny] || map[nx][ny]=='X') continue;
visited[nx][ny] = true;
queue.add(new Pair(nx, ny, temp.t+1, temp.idx));
}
}
queue.clear();
}
Fight f = pq.poll(); //최단시간을 이용해서 보스몬스터와 싸우기
int temp_time = f.t;
int temp_dps = dps[f.idx];
int ans = 1;
while(!pq.isEmpty()) {
f = pq.poll();
hp -= temp_dps*(f.t-temp_time);
temp_time = f.t;
if(hp<0) {
System.out.println(ans);
return;
}
temp_dps += dps[f.idx];
ans++;
}
System.out.println(ans);
}
public static class Pair {
int x;
int y;
int t;
int idx;
public Pair(int x, int y, int t, int idx) {
this.x = x;
this.y = y;
this.t = t;
this.idx = idx;
}
}
public static class Fight implements Comparable<Fight> {
int idx;
int t;
public Fight(int idx, int t) {
this.idx = idx;
this.t = t;
}
public int compareTo(Fight f) {
return this.t > f.t ? 1 : -1;
}
}
}