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

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

20005번: 보스몬스터 전리품

 

🐢해결방법1 (나의 풀이법 - 추천하지 않음)

구현 + BFS로 접근했다. 각 유저들은 1초마다 이동을하고, 보스를 만나면 죽을 때 까지 그자리에서 계속 보스를 때리고, 아직 보스를 만나지 않은 플레이어는 더 이동을 하게 했다.

 

플레이어는 알파벳 소문자로 들어온다고 했으나 순차적이다라는 말은 따로 없었으므로 크기가 26인 배열을 만들었고, 각 플레이어 별로 탐색을 위한 queue와 방문체크를 위한 visited배열을 만들었다.

 

HP가 0이하가 아니라면 보스를 만난 모든 플레이어는 보스를 때리고, 한번이라도 때리면 해당 플레이어를 체크해서 보상 받는 인원 수를 늘려주었다.

 

🐢코드

//package Gold이상문제_정리;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int M, N, P, prizeCnt, HP;
    static char[][] board;
    static boolean[][][] vistied;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static Queue<Pos>[] playerQ = new Queue[26];
    static boolean[] checked;
    static ArrayList<Character> fightPlayers = new ArrayList<>();
    static ArrayList<Character> players = new ArrayList<>();
    static HashMap<Character, Integer> playerDps = new HashMap<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input;
        input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        P = Integer.parseInt(input[2]);
        board = new char[N][M];
        vistied = new boolean[26][N][M];
        checked = new boolean[26];
 
        for (int i = 0; i < 26; i++) {
            playerQ[i] = new LinkedList<>();
        }
 
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = s.charAt(j);
                if (board[i][j] <= 'z' && board[i][j] >= 'a') {
                    int p = board[i][j] - 'a';
                    playerQ[p].add(new Pos(i, j)); // 각 플레이어 별 큐에 플레이어를 담는다
                    players.add(board[i][j]);
                }
            }
        }
 
        for (int i = 0; i < P; i++) {
            input = br.readLine().split(" ");
            char id = input[0].charAt(0);
            int dps = Integer.parseInt(input[1]);
            playerDps.put(id, dps);
        }
        HP = Integer.parseInt(br.readLine());
 
        playGame();
    }
 
    private static void playGame() {
        while (true) {
            playerMove();
            if (!fightBoss())
                break;
        }
        System.out.println(prizeCnt);
    }
 
    private static boolean fightBoss() {
        if (HP > 0) {
            for (char player : fightPlayers) {
                HP -= playerDps.get(player);
                if (!checked[player - 'a']) {
                    checked[player - 'a'] = true;
                    prizeCnt++;
                }
            }
        } else return false;
        return true;
    }
 
    private static void playerMove() {
        for (char player : players) {
            int p = player - 'a';
            Queue<Pos> tmpQ = new LinkedList<>(playerQ[p]); // 각 플레이어 별 Queue를 사용
 
            playerQ[p].clear();
            int t = tmpQ.size();
            loop:
            while (t-- > 0) {
                Pos now = tmpQ.poll();
 
                for (int d = 0; d < 4; d++) {
                    int ny = now.y + dy[d];
                    int nx = now.x + dx[d];
 
                    if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
                    if (board[ny][nx] == 'X') continue;
                    if (vistied[p][ny][nx]) continue;
                    if (board[ny][nx] == 'B') { // 보스를 만나면 해당 플레이어는 탐색 종료
                        fightPlayers.add(player);
                        playerQ[p].clear();
                        break loop;
                    }
                    vistied[p][ny][nx] = true;
                    playerQ[p].add(new Pos(ny, nx));
                }
            }
        }
    }
 
    private static class Pos
    {
        int y, x;
 
        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

즉, 나의 접근법은 각 플레이어별로 Boss를 찾아서 BFS를 돌리고 보스를 만난 플레이어를 체크하도록 했다.

 

🐢 해결방법2 (타 풀이법 참고)

플레이어가 Boss를 찾을수 있다면 Boss도 플레이어를 찾을 수 있으므로 반대로 접근하는 방법이다. BFS를 플레이별로 접근하는 것이 아니라 Boss를 기준으로 BFS를 돌려서 플레이어를 만나면 해당 플레이어를 체크해서 보스와 싸우도록 담고, 이후 체크된 플레이어 수만큼 보상 수를 반환하도록 한다.

 

플레이어를 기준으로 Boss를 찾는 방식보다 Boss를 기준으로 플레이어를 찾는 것이 탐색 경로의 중복이 훨씬 줄게 되므로 메모리도 시간도 훨씬 최적화되어 나온다.

 

🐢 코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Queue;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int M, N, P, prizeCnt, HP;
    static char[][] board;
    static boolean[][] vistied;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static Queue<Pos> queue = new LinkedList<>();
    static boolean[] checked = new boolean[26];
    static ArrayList<Character> fightPlayers = new ArrayList<>();
    static ArrayList<Character> players = new ArrayList<>();
    static HashMap<Character, Integer> playerDps = new HashMap<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input;
        input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        P = Integer.parseInt(input[2]);
        board = new char[N][M];
        vistied = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = s.charAt(j);
                if (board[i][j] == 'B') {
                    vistied[i][j] = true;
                    queue.add(new Pos(i, j)); // 보스를 큐에 넣는다
                }
            }
        }
 
        for (int i = 0; i < P; i++) {
            input = br.readLine().split(" ");
            char id = input[0].charAt(0);
            int dps = Integer.parseInt(input[1]);
            playerDps.put(id, dps);
        }
        HP = Integer.parseInt(br.readLine());
 
        playGame();
        for (int i = 0; i < 26; i++) {
            if (checked[i]) prizeCnt++;
        }
        System.out.println(prizeCnt);
    }
 
    private static void playGame() {
        while (HP > 0)
        {
            int size = queue.size();
 
            while (size-- > 0)
            {
                Pos now = queue.poll();
 
                for (int d = 0; d < 4; d++) {
                    int ny = now.y + dy[d];
                    int nx = now.x + dx[d];
 
                    if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
                    if (board[ny][nx] == 'X') continue;
                    if (vistied[ny][nx]) continue;
                    vistied[ny][nx] = true;
                    queue.add(new Pos(ny, nx));
                    if (board[ny][nx] != '.' && !checked[board[ny][nx] - 'a']) {
                        checked[board[ny][nx] - 'a'] = true;
                        fightPlayers.add(board[ny][nx]); //플레이어를 만나면 보스랑 싸우도록 담는다
                    }
                }
            }
 
            for (char player : fightPlayers) // 보스랑 싸움
                HP -= playerDps.get(player);
        }
    }
 
    private static class Pos {
        int y, x;
 
        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

 

문제를 읽으면서 플레이어가 보스를 찾으러 이동한다고 해서 바로 그대로 구현하지 말고 좀 더 최적화 할 수 있도록 생각을 더 하자