알고리즘

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

박카스마시며코딩 2023. 5. 4. 14:05

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

 

20005번: 보스몬스터 전리품

입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입

www.acmicpc.net

[풀이1]

저는 우선순위 큐와 BFS를 통해 문제를 해결하였습니다.

각각의 플레이어 위치에서 B로 얼마나 걸리는지 BFS를 통해 확인하고 이를 우선순위 큐에 넣었습니다.

우선순위 큐에서 도착시간이 적은 순서대로 가져오고 이를 보스몬스터에 이전 시간의 갭 차이 시간만큼 이전 데미지합을 주고 체력이 0보다 크다면 해당 인원도 전리품을 취득할 수 있다고 판단하였습니다.

 

[풀이2]

문제를 풀고 다시 생각해보니 굳이 각각의 지점에서 B로 얼마나 걸리는지 확인하기 보다 B에서 각각의 지점이 얼마나 걸리는지 확인하는 것이 더 빠를 것 같다고 생각하였습니다. 나머지 풀이는 같게 하였습니다. 그 결과 시간,메모리 둘다 확연히 줄어드는 것을 확인할 수 있었습니다. 

[풀이1]

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_20005 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int cnt = stoi.apply(st.nextToken());
        char[][] map = new char[n][m];
        for(int i = 0 ; i < n ; i++){
            String str = br.readLine();
            for(int j = 0 ; j < m ; j++){
                map[i][j] = str.charAt(j);
            }
        }
        Map<Character,Integer> dps = new HashMap<> ();
        for(int i = 0 ; i < cnt ; i++){
            st = new StringTokenizer(br.readLine());
            char ch = st.nextToken().charAt(0);
            int damage = stoi.apply(st.nextToken());
            dps.put(ch,damage);
        }
        int hp = stoi.apply(br.readLine());
        int result = cal(map,n,m,dps,hp);
        System.out.println(result);
    }
    private static final char EMPTY = '.';
    private static final char BLOCK = 'X';
    private static final char BOSS = 'B';
    private static class Node{
        char ch;
        int time;

        public Node(char ch, int time) {
            this.ch = ch;
            this.time = time;
        }
    }
    private static int cal(char[][] map, int n, int m, Map<Character, Integer> dps, int hp) {
        int cnt = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>((v1,v2)->{
            return v1.time - v2.time;
        });
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(map[i][j] != EMPTY && map[i][j] != BLOCK && map[i][j] != BOSS){
                    int time = bfs(i,j,n,m,map);
                    pq.offer(new Node(map[i][j],time));
                }
            }
        }
        int prevTime = 0;
        int damageSum = 0;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            hp -= damageSum * (node.time - prevTime);
            if(hp <= 0){
                break;
            }
            cnt++;
            prevTime = node.time;
            damageSum += dps.get(node.ch);
        }
        return cnt;
    }
    private static final int[] DY = {-1,0,1,0};
    private static final int[] DX = {0,1,0,-1};
    private static int bfs(int y, int x, int n,int m,char[][] map) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{y,x});
        boolean[][]visited = new boolean[n][m];
        visited[y][x] = true;
        int time = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int[] now = q.poll();
                if(map[now[0]][now[1]] == BOSS){
                    return time;
                }
                for(int i = 0 ; i < 4; i++){
                    int ny = now[0] + DY[i];
                    int nx = now[1] + DX[i];
                    if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[ny][nx] != BLOCK && !visited[ny][nx]){
                        visited[ny][nx] = true;
                        q.offer(new int[]{ny,nx});
                    }
                }
            }
            time++;
        }
        return -1;
    }

}

 

[풀이2]

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_20005_2 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int cnt = stoi.apply(st.nextToken());
        char[][] map = new char[n][m];
        for(int i = 0 ; i < n ; i++){
            String str = br.readLine();
            for(int j = 0 ; j < m ; j++){
                map[i][j] = str.charAt(j);
            }
        }
        Map<Character,Integer> dps = new HashMap<> ();
        for(int i = 0 ; i < cnt ; i++){
            st = new StringTokenizer(br.readLine());
            char ch = st.nextToken().charAt(0);
            int damage = stoi.apply(st.nextToken());
            dps.put(ch,damage);
        }
        int hp = stoi.apply(br.readLine());
        int result = cal(map,n,m,dps,hp);
        System.out.println(result);
    }
    private static final char EMPTY = '.';
    private static final char BLOCK = 'X';
    private static final char BOSS = 'B';
    private static class Node{
        char ch;
        int time;

        public Node(char ch, int time) {
            this.ch = ch;
            this.time = time;
        }
    }
    private static int cal(char[][] map, int n, int m, Map<Character, Integer> dps, int hp) {
        int cnt = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>((v1,v2)->{
            return v1.time - v2.time;
        });
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(map[i][j] == BOSS){
                    pq = bfs(i,j,n,m,map);
                }
            }
        }
        int prevTime = 0;
        int damageSum = 0;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            hp -= damageSum * (node.time - prevTime);
            if(hp <= 0){
                break;
            }
            cnt++;
            prevTime = node.time;
            damageSum += dps.get(node.ch);
        }
        return cnt;
    }
    private static final int[] DY = {-1,0,1,0};
    private static final int[] DX = {0,1,0,-1};
    private static PriorityQueue bfs(int y, int x, int n,int m,char[][] map) {
        Queue<int[]> q = new LinkedList<>();
        PriorityQueue<Node> pq = new PriorityQueue<>((v1,v2)->{
            return v1.time-v2.time;
        });
        q.offer(new int[]{y,x});
        boolean[][]visited = new boolean[n][m];
        visited[y][x] = true;
        int time = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int[] now = q.poll();
                if(map[now[0]][now[1]] != EMPTY && map[now[0]][now[1]] != BLOCK && map[now[0]][now[1]] != BLOCK &&
                map[now[0]][now[1]] != BOSS){
                    pq.offer(new Node(map[now[0]][now[1]],time));
                }
                for(int i = 0 ; i < 4; i++){
                    int ny = now[0] + DY[i];
                    int nx = now[1] + DX[i];
                    if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[ny][nx] != BLOCK && !visited[ny][nx]){
                        visited[ny][nx] = true;
                        q.offer(new int[]{ny,nx});
                    }
                }
            }
            time++;
        }
        return pq;
    }

}

'알고리즘' 카테고리의 다른 글

프로그래머스 커피 심부름(JAVA)  (0) 2023.05.06
프로그래머스 문자열 나누기 (JAVA)  (0) 2023.05.05
프로그래머스 코드 처리하기 (JAVA)  (0) 2023.05.03
프로그래머스 그림 확대 (JAVA)  (0) 2023.05.02
프로그래머스 혼자 놀기의 달인 (JAVA)  (0) 2023.05.01

'알고리즘'의 다른글

  • 현재글백준 20005번 보스몬스터 전리품 (JAVA)

관련글

티스토리툴바