[백준]20005: 보스몬스터 전리품 - JAVA

[백준]20005: 보스몬스터 전리품

20005번: 보스몬스터 전리품

풀이

🪑 입력받는 정보가 많아서 복잡해 보이지만 알고보면 구현 + BFS문제였다.

 

문제의 조건을 정리해 보자.

• 전리품은 한 번이라도 피해를 준 플레이어에게 지급된다.
• 최대 몇명의 플레이어가 전리품을 가져갈 수 있는지 알아낸다.
• 각각의 플레이어는 보스에게 최단거리로 이동하여 보스 칸에 도달하자마자 공격을 시작한다.
• 플레이어의 공격은 동시에 이뤄지며 같은 위치에 여러 플레이어가 위치할 수 있다.
• 플레이어는 상, 하, 좌, 우로 이동 가능하다.

 

 

🔧 문제 풀이 순서를 생각해 보자.

1. 플레이어의 위치를 기준으로 탐색을 해야 하므로 플레이어의 위치를 따로 저장한다.
2. 각각의 플레이어의 정보를 저장한다.
3. BFS탐색으로 플레이어에서 보스까지 최단 경로를 탐색한다.
4. 보스에게 도달한 플레이어는 공격을 한다.
5. 보스에게 한 번이라도 공격한 플레이어의 수를 반환한다.

 

🔹 플레이어의 위치를 따로 저장한다.

- 이 부분은 멤멤월드의 정보를 입력받을때 저장해 주었다.

- 현재 입력받는 정보가 '.', 'X', 'B'가 아닌 경우라면 플레이어 이므로 해당 위치와 플레이어 id를 저장하는 Node class를 만들어 저장해 주었다.

- 플레이어 위치부터 BFS 탐색을 해야 하므로 플레이어를 입력받는 즉시 q에 담아주었다.

 

🔹 각각의 플레이어의 정보를 저장한다.

- 이제 플레이어 별로 dps정보가 주어진다.

- 이때 플레이어 정보를 저장하기 위해 Player class를 만들어주었다.

- 플레이어 정보는 HashMap으로 저장해 주었는데, 이때 각 플레이어를 입력받는 순서대로 0번부터 고유의 인덱스를 부여해 주었다. 이렇게 한 이유는 BFS 탐색을 하면서 방문체크할 때 각각의 플레이어 인덱스를 사용하여 방문체크 해 줄 예정이기 때문이다.

 

🔹 BFS탐색으로 플레이어에서 보스까지 최단 경로를 탐색한다.

- 각각의 플레이어 마다 방문 체크를 따로 해줘야 하므로 visited 배열을 3차원으로 만들어 주었다. 이때 마지막 인덱스는 플레이어의 고유한 인덱스를 의미한다.

- 플레이어는 동시에 같은 시간만큼 이동해야 한다. 그러므로 q의 사이즈 만큼 모두 함께 이동을 시켜준다.

- 이미 보스에 도달한 플레이어는 더 이상 탐색하지 않아도 되므로 넘어간다.

- 아직 보스에 도달하지 않은 플레이어를 상, 하, 좌, 우 방향중 이동할 수 있는 방향으로 이동시킨다.

- 플레이어가 이동 중에 보스를 만난다면 해당 플레이어를 공격한 플레이어 리스트에 추가해 준다.

 

🔹 보스에게 도달한 플레이어는 공격을 한다.

- 공격시에는 attack 리스트에 담아둔 플레이어의 정보를 사용하여 공격한다.

- HashMap에서 현재 플레이어에 해당하는 dps 정보를 가지고 와 보스의 hp에서 dps만큼 깎아 준다.

 

🔹 보스에게 한 번이라도 공격한 플레이어의 수를 반환한다.

- attack 리스트의 크기를 반환해 주면 된다.

 

코드

import java.util.*;
 
public class Main {
 
    static int m, n, p;
    static Map<Character, Player> playerMap;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static Queue<Node> q;
    static char[][] board;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        m = scan.nextInt();
        n = scan.nextInt();
        p = scan.nextInt();
 
        board = new char[m][n];
        q = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            String str = scan.next();
            for(int j = 0; j < n; j++) {
                board[i][j] = str.charAt(j);
                if(board[i][j] != '.' && board[i][j] != 'B' && board[i][j] != 'X') {
                    q.add(new Node(board[i][j], i, j));
                }
            }
        }
 
        playerMap = new HashMap<>();
        int num = 0; //playser에게 고유 번호를 부여함.
        for(int i = 0; i < p; i++) {
            char id = scan.next().toCharArray()[0];
            int dps = scan.nextInt();
            playerMap.put(id, new Player(num++, dps));
        }
        int boss_hp = scan.nextInt();
        //입력 끝
 
        System.out.println(bfs(boss_hp));
    }
 
    public static int bfs(int boss_hp) {
        boolean[][][] visited = new boolean[m][n][p];
        ArrayList<Character> attack = new ArrayList<>(); //공격할 수 있는 플레이어
        
        while(boss_hp > 0) {   
            int q_size = q.size();
            while(q_size > 0) {
                Node current = q.poll();
                q_size--;
 
                if(attack.contains(current.id)) continue; //이미 보스에 도달한 플레이어인 경우
                else {
                    for(int i = 0; i < 4; i++) {
                        int nx = current.x + dx[i];
                        int ny = current.y + dy[i];
                        if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                        if(visited[nx][ny][playerMap.get(current.id).num] || board[nx][ny] == 'X') continue;
                        
                        visited[nx][ny][playerMap.get(current.id).num] = true;
                        if(board[nx][ny] == 'B') attack.add(current.id);
                        else q.offer(new Node(current.id, nx, ny));
                    }
                }
            }
            for(char p : attack) { //공격
                boss_hp -= playerMap.get(p).dps;
            }
        }
        return attack.size();
    }
 
    public static class Node {
        char id;
        int x;
        int y;
        
        public Node(char id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }
    }
 
    public static class Player {
        int num;
        int dps;
 
        public Player(int num, int dps) {
            this.num = num;
            this.dps = dps;
        }
    }
}