[알고리즘][X] 전투 로봇

https://www.codetree.ai/training-field/frequent-problems/problems/fighting-robot/description?page=3&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int[] robot;
    static int N;
    static Monster[][] map;
    static PriorityQueue<Monster> monsters = new PriorityQueue<>();
    static int sum = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new Monster[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int value = Integer.parseInt(st.nextToken());
                if (value == 9) {
                    robot = new int[]{i, j, 2, 0};
                    map[i][j] = new Monster(i, j, 0, false);
                    continue;
                }

                map[i][j] = new Monster(i, j, value, false);
                if (value > 0) {
                    monsters.add(map[i][j]);
                }

            }
        }

        while (game()) {

        }
        System.out.println(sum);
    }

    private static boolean game() {
        while (true) {
            if (monsters.isEmpty()) {
                break;
            }
            Monster cur = monsters.peek();
            if (robot[2] > cur.level) {
                map[cur.r][cur.c].possible = true;
                monsters.poll();
            } else {
                break;
            }
        }

        // return: dist, r, c, idx
        int rx = robot[0];
        int ry = robot[1];

        Queue<int[]> queue = new ArrayDeque<>();
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        boolean[][] visited = new boolean[N][N];
        queue.add(new int[]{rx, ry, 0});
        visited[rx][ry] = true;
        PriorityQueue<int[]> candidates =new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    if (o1[1] == o2[1]) {
                        return o1[2] - o2[2];
                    }
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            int dist = cur[2];

            if (map[x][y].possible) {
                candidates.add(new int[]{dist, x, y});
            }
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny] && robot[2] >= map[nx][ny].level) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, cur[2] + 1});
                }
            }
        }

        if (candidates.isEmpty()) {
            return false;
        } else {
            int[] cur = candidates.poll();
            int x = cur[1];
            int y = cur[2];

            sum += cur[0];
            map[x][y].possible = false;
            robot[3]++;
            if (robot[2] == robot[3]) {
                robot[2]++;
                robot[3] = 0;
            }
            robot[0] = x;
            robot[1] = y;
            return true;
        }
    }

    static class Monster implements Comparable<Monster> {

        int r;
        int c;
        int level;
        boolean possible;

        public Monster(int r, int c, int level, boolean possible) {
            this.r = r;
            this.c = c;
            this.level = level;
            this.possible = possible;
        }

        @Override
        public int compareTo(Monster o) {
            return level - o.level;
        }
    }
}

나의 풀이

- 좌표적으로나 거리적으로나 우선순위가 존재한다면 웬만해서는 정렬을 해주는게 좋다고 생각한다.

- 왜냐하면 그렇게 안하고 탐색 순서로 할 수 있다고 착각을 해서 결국 틀렸기 때문이다.