백준 20005번: 보스몬스터 전리품

문제 설명

• https://www.acmicpc.net/problem/20005
• 유저는 1초에 한칸을 이동합니다.
  유저가 보스칸에 도착하면 매초 자신이 가진 dps만큼 보스의 체력을 깎습니다.
  보스의 체력이 0이되면 레이드가 종료됩니다.
  레이드에 참여한 유저를 구하는 문제입니다.

접근법

• 유저마다 방문상태를 체크하기 위해 3차원 배열을 사용했습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, -1, 0, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		Queue<Node> q = new LinkedList<Node>();
		boolean[][][] v = new boolean[N][M][P];

		char[][] board = new char[N][M];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				char c = s.charAt(j);
				board[i][j] = c;
				if (c != 'B' && c != '.' && c != 'X') {
					q.add(new Node(c, i, j));
					v[i][j][c - 'a'] = true;
				}
			}
		}
		HashMap<String, Integer> dps = new HashMap<String, Integer>();
		for (int i = 0; i < P; i++) {
			st = new StringTokenizer(br.readLine());
			dps.put(st.nextToken(), Integer.parseInt(st.nextToken()));
		}
		int hp = Integer.parseInt(br.readLine());

		System.out.println(BFS(board, q, 0, dps, hp, v));
	}

	public static int BFS(char[][] board, Queue<Node> q, int totalDps, HashMap<String, Integer> dps, int hp,
			boolean[][][] v) {
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			while (--size >= 0) {
				Node now = q.poll();
				if (board[now.x][now.y] == 'B') {
					cnt++;
					totalDps += dps.get(Character.toString(now.who));
					continue;
				}
				for (int d = 0; d < 4; d++) {
					int nx = now.x + dx[d];
					int ny = now.y + dy[d];
					if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] != 'X' && !v[nx][ny][now.who - 'a']) {
						v[nx][ny][now.who - 'a'] = true;
						q.add(new Node(now.who, nx, ny));
					}
				}
			}
			hp -= totalDps;
			if (hp <= 0)
				return cnt;
		}

		return cnt;
	}

	static class Node {
		char who;
		int x;
		int y;

		@Override
		public String toString() {
			return "Node [who=" + who + ", x=" + x + ", y=" + y + "]";
		}

		public Node(char who, int x, int y) {
			super();
			this.who = who;
			this.x = x;
			this.y = y;
		}
	}
}