백준 20005 <보스몬스터 전리품>

 

이문제는 BFS를 이용해 보스 몬스터까지 가는 가까운 거리를 알아내고 몬스터의 피를 줄여나가는 시뮬레이션 문제이다.

 

문제 풀이

1. 보스몬스터 위치에서 BFS를 하여 각각의 플레이어까지 가는 최소 시간을 Queue에 넣는다.
2. Queue에서 꺼내면서 같은 시간이 걸리면 계속 꺼내 주고 체력을 얼마만큼 깎을 수 있는지 계산한다.
3. 몬스터의 피가 음수가 되면 break를 해준다.

플레이어의 id를 key로 dps를 value로 해서 Hashmap 에 저장을 해서 꺼내서 계산해준다.

 

 

보스의 위치에서 BFS를 하기위한 클래스를 선언

그렇다면 q에 보스에서 가장 짧게 걸리는 플레이어 순대로 이름과 걸리는 시간이 적혀있게 된다.

 

초기 값은 result를 0에서 1을 더해주고

 

깎을 수 있는 체력의 합을 더한 sum을 선언해주고 가장 짧게 걸리는 시간을 꺼내고 같으면 계속 꺼내서 sum에 더해준다.

이렇게 다음 큐를 꺼내면서 계산을 해주면 된다.

 

이 문제의 주의 사항은 같은 시간 내에 적에게 도달할 경우가 있다는 것이다!

 

전체 코드

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

public class Main {

	public static class time{
		int x;
		int y;
		int t;
		public time(int x, int y, int t) {
			super();
			this.x = x;
			this.y = y;
			this.t = t;
		}
		
	}
	public static class catc{
		char name;
		int time;
		public catc(char name,int time) {
			super();
			this.time = time;
			this.name = name;
		}
		
	}
	static boolean visit[][];
	static int m,n,p,hp,dir[][]= {{-1,0},{0,1},{1,0},{0,-1}},sx,sy,result;
	static String map[];
	static HashMap<Character,Integer> h;
	static Queue<catc> q;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		m=Integer.parseInt(st.nextToken());
		n=Integer.parseInt(st.nextToken());
		p=Integer.parseInt(st.nextToken());
		map=new String[m];
		visit=new boolean[m][n];
		h=new HashMap<Character,Integer>();
		q=new LinkedList<catc>();	
		for(int i=0;i<m;i++) {
			map[i]=br.readLine();
			for(int j=0;j<n;j++) {
				if(map[i].charAt(j)=='B') {
					sx=i;
					sy=j;
				}
			}
		}
		for(int i=0;i<p;i++) {
			st = new StringTokenizer(br.readLine());
			char ID=st.nextToken().charAt(0);
			int dps=Integer.parseInt(st.nextToken());
			h.put(ID, dps);
		}
		hp=Integer.parseInt(br.readLine());
		bfs();//각각의 시간을 알기위해서
		find();
		
	}
	private static void find() {
		// TODO Auto-generated method stub
		result++;
		int sum=0;
		catc ftime=q.remove();
		sum+=h.get(ftime.name);
		while(!q.isEmpty()&&q.peek().time==ftime.time) {
			result++;
			ftime=q.remove();
			sum+=h.get(ftime.name);
		}
		while(!q.isEmpty()) {
			int can=0;
			int si=0;
			catc next=q.remove();
			can+=h.get(next.name);
			si++;
			while(!q.isEmpty()&&q.peek().time==next.time) {
				next=q.remove();
				can+=h.get(next.name);
				si++;
			}
			hp-=(sum*(next.time-ftime.time));
			sum+=can;
			ftime=next;
			if(hp<0) {
				break;
			}
			else {
				result+=si;
			}
			
		}
		System.out.println(result);
		
	}
	private static void bfs() {
		// TODO Auto-generated method stub
		Queue<time> qu=new LinkedList<time>();	
		qu.add(new time(sx,sy,0));
		visit[sx][sy]=true;
		while(!qu.isEmpty()) {
			time next=qu.remove();
			for(int i=0;i<4;i++) {
				int x=next.x+dir[i][0];
				int y=next.y+dir[i][1];
				if(x<0||x>=m||y<0||y>=n)
					continue;
				if(visit[x][y]||map[x].charAt(y)=='X')
					continue;
				visit[x][y]=true;
				if(map[x].charAt(y)>='a'&&map[x].charAt(y)<='z') {
					q.add(new catc(map[x].charAt(y),next.t+1));
				}
				qu.add(new time(x,y,next.t+1));
			}
		}
		
	}
	

}