[BOJ] 20005.보스몬스터 전리품(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

1초 동안 모든 동작(이동, 공격)이 이루어져야 한다.

전리품을 가져갈 수 있는 플레이어 수의 최댓값을 구하기 위해서는

플레이어들이 보스몬스터에 '최단 거리'로 도달해야 한다.

보스몬스터에게 '최단 거리'로 이동하기 위해 BFS로 이동을 해보자.

* 보스몬스터를 공격해서 전리품 수령이 확정된 플레이어 상태를 관리해야 한다.

* 1초동안

[이동]

- 전리품 수령이 확정된 플레이어는 더이상 이동할 필요가 없다.

- 보스몬스터의 위치에 도달했을 경우 전리품 수령을 확정시켜주고 플레이어 수 count

- 보스몬스터의 위치에 도달하지 못했을 경우 이동

[공격]

- 전리품 수령이 확정된 플레이어는 계속 몬스터를 공격

- 몬스터의 체력이 바닥날 때까지 동작은 반복

#. Code

26명의 플레이어가 M*N의 map을 이동한다.

O(M*N*26)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ20005 {       static int M, N, P, power[], bossHp;     static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 };     static char map[][];     static boolean[][][] visited;     static Queue<Player> q;       public static void main(String[] args) throws IOException {           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 char[M][N];         power = new int[P]; // player의 dps 정보         visited = new boolean[P][M][N];           // Set map         q = new LinkedList<>();         for (int i = 0; i < M; i++) {             String input = br.readLine();             for (int j = 0; j < N; j++) {                 map[i][j] = input.charAt(j);                 // player의 위치가 등록된다면                 if (map[i][j] >= 'a' && map[i][j] <= 'z') {                     q.add(new Player(map[i][j] - 'a', i, j));                     visited[map[i][j] - 'a'][i][j] = true;                 }             }         }           // Set player power         for (int i = 0; i < P; i++) {             st = new StringTokenizer(br.readLine());             char a = st.nextToken().charAt(0);             int b = Integer.parseInt(st.nextToken());             power[a - 'a'] = b;         }           bossHp = Integer.parseInt(br.readLine());           System.out.println(process());     }       private static int process() {           // 전리품을 받은 플레이어         boolean[] selected = new boolean[P];         int cnt = 0;           while (bossHp > 0) {               int size = q.size();             while (size-- > 0) {                   Player now = q.poll();                 // 이미 전리품 수령이 확정된 플레이어일 경우 pass                 if (selected[now.id]) continue;                 // 보스의 위치에 도달했을 경우                 if (map[now.r][now.c] == 'B') {                     selected[now.id] = true;                     cnt++;                 }                 // 보스와 다른 위치에 있을 경우 이동                 for (int d = 0; d < 4; d++) {                     int rr = now.r + dr[d];                     int cc = now.c + dc[d];                     // 범위를 벗어날 경우                     if (rr < 0 || cc < 0 || rr >= M || cc >= N) continue;                     // 이미 방문했거나 이동할 수 없는 경우                     if (visited[now.id][rr][cc] || map[rr][cc] == 'X') continue;                       visited[now.id][rr][cc] = true;                     q.add(new Player(now.id, rr, cc));                 }             }               // 다같이 보스 공격!             for (int i = 0; i < P; i++) {                 if(selected[i]) bossHp -= power[i];             }         }                  return cnt;     }       static class Player {         int id, r, c;           public Player(int id, int r, int c) {             this.id = id;             this.r = r;             this.c = c;         }       } }   Colored by Color Scripter

cs

#. Code_v2

플레이어가 이동하는 방식이 아닌

몬스터가 이동하는 방식으로 해결한 방법이다.

몬스터가 이동하다가 플레이어를 만나면 

해당 플레이어는 전리품 수령 대상이 된다.

최대 26명의 플레이어가 모두 이동하는게 아닌 몬스터 1명만 이동하는

굉장히 참신한 해결 방법이다.

플레이어가 이동 : O(M*N*26)

보스몬스터 이동 : O(M*N)

나도 문제를 너무 어렵게 생각하지만 말고

문제를 바라보는 시야를 넓히는 연습을 해야겠다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ20005_v2 {
 
    static int M, N, P, power[];
    static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 };
    static char map[][];
 
    public static void main(String[] args) throws IOException {
 
        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 char[M][N];
        power = new int[P]; // player의 dps 정보
 
        // Set map
        int bossR = 0, bossC = 0;
        for (int i = 0; i < M; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = input.charAt(j);
                // Boss의 위치
                if (map[i][j] == 'B') {
                    bossR = i;
                    bossC = j;
                }
            }
        }
 
        // Set player power
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());
            char a = st.nextToken().charAt(0);
            int b = Integer.parseInt(st.nextToken());
            power[a - 'a'] = b;
        }
 
        int bossHp = Integer.parseInt(br.readLine());
 
        System.out.println(process(bossR, bossC, bossHp));
    }
 
    private static int process(int R, int C, int HP) {
 
        // 전리품을 받을 플레이어
        boolean[] selected = new boolean[P];
        boolean[][] visited = new boolean[M][N];
        int cnt = 0;
        // 보스의 출발점
        Queue<Boss> q = new LinkedList<>();
        q.add(new Boss(R, C));
        visited[R][C] = true;
 
        while (HP > 0) {
 
            int size = q.size();
            while (size-- > 0) {
 
                Boss now = q.poll();
                // 플레이어의 위치에 도달했을 경우
                if (map[now.r][now.c] >= 'a' && map[now.r][now.c] <= 'z') {
                    // 해당 플레이어를 전리품 수령 대상에 포함
                    selected[map[now.r][now.c] - 'a'] = true;
                    cnt++;
                }
                // 보스의 이동
                for (int d = 0; d < 4; d++) {
                    int rr = now.r + dr[d];
                    int cc = now.c + dc[d];
                    // 범위를 벗어날 경우
                    if (rr < 0 || cc < 0 || rr >= M || cc >= N) continue;
                    // 이미 방문했거나 이동할 수 없는 경우
                    if (visited[rr][cc] || map[rr][cc] == 'X') continue;
 
                    visited[rr][cc] = true;
                    q.add(new Boss(rr, cc));
                }
            }
 
            // 다같이 보스 공격!
            for (int i = 0; i < P; i++) {
                if (selected[i]) HP -= power[i];
            }
        }
 
        return cnt;
    }
 
    static class Boss {
        int r, c;
 
        public Boss(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
}