[백준 20005] 보스몬스터 전리품 (JAVA)

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

 

난이도
221225 기준 골드 3

사용 알고리즘
bfs

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

20005번: 보스몬스터 전리품

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

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

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

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

 단, 모든 플레이어는 보스몬스터가 소환되면 보스몬스터의 위치로 최대한 빠른 경로로 이동하며 이동한 경우 공격을 바로 시작한다. 공격에 소모되는 시간은 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는 정수이다.

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

 

출력

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

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 각 플레이어가 보스 몬스터까지 갈 수 있는 최단거리는 bfs를 이용하면 구할 수 있을 것입니다. 나머지는 구현하기에 달렸습니다. 시뮬레이션을 위해 HashMap도 사용하면 좋을 것 같아요.

 

 

3. 풀이 구상

 

 먼저 보스몬스터를 시작점으로 각 플레이어까지의 최단거리를 구합니다. 이게 가능한 이유는 문제 조건에 "한 지점에 여러명의 플레이어가 위치할 수 있다" 가 있기에 플레이어가 이동하면서 겹치는 경우를 따로 처리 할 필요가 없기 때문입니다. 이 조건이 없었다면 상당히 골치 아픈 문제가 되었겠네요.

 각 플레이어까지의 최단거리를 구하고 시간을 1초씩 늘리며 시뮬레이션을 하면 됩니다.

 시간 복잡도에서 최악의 경우가 HP가 1000000인 보스몬스터와 거리가 1000*1000 위치에 있는 캐릭터의 dps가 1 인경우인데요 이래도 시뮬레이션은 2,000,000초까지만 진행 되기에 시뮬레이션을 1초씩 해도 시간 초과에서는 문제가 안날 것입니다.

 보스 클래스와 플레이어 클래스 그리고 좌표값을 담을 RC 클래스를 만들어 구현할 예정입니다.

 여기까지만 구상하고 문제를 풀어보겠습니다.

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

// 백준 20005 보스몬스터 전리품
public class Main {

	static int M, N, P;
	static char[][] worldMap;
	static int[][] steps;
	static Boss boss;
	static Player[] players;
	static HashMap<Integer,List<Integer>> hm;
	
	static class Boss {
		
		int r;
		int c;
		int HP;
		
		public Boss(int r, int c) {
			this.r = r;
			this.c = c;
		}

		public int getHP() {
			return HP;
		}

		public void setHP(int hP) {
			HP = hP;
		}
		
		
	}
	
	static class Player{
		
		char name;
		
		int r;
		int c;
		
		int distWithBoss;
		
		int dps;

		public Player(char name, int r, int c) {
			this.name = name;
			this.r = r;
			this.c = c;
		}

		public int getDps() {
			return dps;
		}

		public void setDps(int dps) {
			this.dps = dps;
		}

		public int getDistWithBoss() {
			return distWithBoss;
		}

		public void setDistWithBoss(int distWithBoss) {
			this.distWithBoss = distWithBoss;
		}
		
	}
	
	static class RC{
		
		int r;
		int c;
		
		public RC(int r, int c) {
			this.r = r;
			this.c = c;
		}
		
		
	}
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	N = Integer.parseInt(st.nextToken());
    	P = Integer.parseInt(st.nextToken());
    	
    	worldMap = new char[M][N];
    	steps = new int[M][N];
    	players = new Player[27];
    	hm = new HashMap<Integer,List<Integer>>();
    	
    	for(int r = 0; r < M; r++) {
    		String str = br.readLine();
    		for(int c = 0; c < N; c++) {
    			char cur = str.charAt(c);
    			worldMap[r][c	] = cur;
    			if(cur == 'B') {
    				boss = new Boss(r,c);
    			} else if(cur != '.' && cur != 'X') {
    				players[cur-'a'] = new Player(cur,r,c);
    			}
    		}
    	}
    	
    	for(int i = 0; i < P; i++) {
    		st = new StringTokenizer(br.readLine());
    		
    		String name = st.nextToken();
    		
    		players[name.charAt(0)-'a'].setDps(Integer.parseInt(st.nextToken()));
    	}
    	
    	boss.setHP(Integer.parseInt(br.readLine()));
    	
    	
    	bossbfs();
    	
    	int resultPlayerCnt = 0;
    	int dpssum = 0;
    	int time = 1;
    	
    	while(boss.getHP()>0) {
    		
    		if(hm.containsKey(time)) {
    			List<Integer> curls = hm.get(time);
    			int size = curls.size();
   				resultPlayerCnt += size;
   				for(int i = 0; i < size; i++) {
   					dpssum += curls.get(i);
   				}
    		}
    		
    		boss.setHP(boss.getHP()-dpssum);
    		time++;
    	}
    	
    	bw.write(resultPlayerCnt+"");
    	bw.flush();
        bw.close();
        br.close();
    }
    	
    // 상하좌우
    static int dr[] = {-1,1,0,0};
    static int dc[] = {0,0,-1,1};
    
    static void bossbfs() {
    	
    	Queue<RC> q = new LinkedList<RC>();
    	RC bossrc = new RC(boss.r,boss.c);
    	q.offer(bossrc);
    	// 일단은 1로 시작하고 밑에서 스텝 계산할때는 다 -1 시켜줄 것
    	// 0으로 시작하면 boss처음 위치가 방문 했는지 판단할때 조금 꼬임
    	steps[boss.r][boss.c] = 1;
    	
    	int playerCnt = 0;
    	
    	while(q.size()>0 && playerCnt<P) {
    		RC cur = q.poll();
    		
    		int curr = cur.r;
    		int curc = cur.c;
    		
    		int curstep = steps[curr][curc];
    		
    		for(int d = 0; d < 4; d++) {
    			int nr = curr + dr[d];
    			int nc = curc + dc[d];
    			
    			// steps가 0인지 아닌지로 visited까지 판단
    			if(inRange(nr,nc) && worldMap[nr][nc]!='X' && steps[nr][nc]==0) {
    				steps[nr][nc] = curstep+1;
    				if(worldMap[nr][nc]!='B' && worldMap[nr][nc]!='.') {
    					char curPlayer = worldMap[nr][nc];
    					players[curPlayer-'a'].distWithBoss = steps[nr][nc]-1;
    					if(hm.containsKey(steps[nr][nc]-1)) {
    						hm.get(steps[nr][nc]-1).add(players[curPlayer-'a'].dps);
    					} else {
    						List<Integer> dpsls = new ArrayList<>();
    						dpsls.add(players[curPlayer-'a'].dps);
    						hm.put(steps[nr][nc]-1, dpsls);
    					}
    					
    					playerCnt++;
    				}
    				q.offer(new RC(nr,nc));
    			}
    		}
    		
    	}
    	
    }
    
    static boolean inRange(int nr, int nc) {
    	if(nr >= 0 && nr < M && nc >= 0 && nc < N) {
    		return true;
    	} else {
    		return false;
    	}
    }

}

 

 

2. 오답노트

 

 문제에 1000초까지만 시뮬레이션한다는 조건이 없었는데 뭐에 홀렸는지 1000초까지만 시뮬레이션을 해서 두 번이나 틀렸습니다. 문제에 중요한 부분 굵은 표시를 하면 뭐 합니까 문제를 제대로 안읽고 틀리는 건 가장 바보같은 실수입니다 흑흑 난 바보야.

 

풀이 후기

 혹시나 이번 문제를 풀고 게임 구현 문제를 제대로 한번 풀어보고 싶은 생각이 드셨다면

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

17081번: RPG Extreme

이 RPG Extreme 문제 추천합니다 플래티넘 2의 난이도 답게 엄청나게 복잡하지만 풀어내신다면 어떤 구현 문제가 나와도 푸실 수 있을 거에요