[Code Tree] 포탑 부수기(Java)

문제

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20

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

풀이

[자료 구조]

- int[][] DELTAS_FOR_ATTACK1: 레이저 공격을 위한 사방 이동 좌표

- int[][] DELTAS_FOR_ATTACK2: 포탄 공격을 위한 팔방 이동 좌표

- PriorityQueue<int[]> WEAKEST: 공격자 선정을 위한 최소힙

    - 공격력 오름차순 정렬(공격력 가장 작은 포탑)

    - 공격력이 같으면 마지막 공격 시간 내림차순 정렬(가장 최근에 공격한 포탑)

    - 마지막 공격 시간 같으면 행과 열의 합 내림차순 정렬(행과 열의 합이 가장 큰 포탑)

    - 행과 열의 합이 같으면 열 내림차순 정렬(열이 가장 큰 포탑)

- PriorityQueue<int[]> STRONGEST: 공격 대상 선정을 위한 최대힙

    - 공격력 내림차순 정렬(공격력 가장 큰 포탑)

    - 공격력이 같으면 마지막 공격 시간 오름차순 정렬(가장 오래전에 공격한 포탑)

    - 마지막 공격 시간 같으면 행과 열의 합 오름차순 정렬(행과 열의 합이 가장 작은 포탑)

    - 행과 열의 합이 같으면 열 오름차순 정렬(열이 가장 작은 포탑)

- PriorityQueue<int[]> MOVES: 레이저 공격을 위한 최단거리를 구하기 위한 최소힙

    - 공격자로부터 공격 대상까지의 거리 오름차순 정렬

    - 공격자로부터 공격 대상까지의 거리 같으면 방향 오름차순 정렬(우->하->좌->상 우선순위)

        - 우: 0, 하: 1, 좌: 2, 상: 3으로 각 이동에 대한 방향을 숫자로 표현(지금까지의 이동방향 * 10 + 현재 이동방향)

- int[][][] map: 

    - 0번 인덱스: 공격력

    - 1번 인덱스: 마지막 공격 시간

- int[][] distances: 해당 좌표에서의 최단거리

- int[][] roots: 해당 좌표까지 최단거리로 온 직전 좌표

- boolean[][] isVisited: 최단 경로 파악 중 해당 좌표 방문 여부

- boolean[][] isRelated: 공격자, 공격 대상자, 공격관련자들인지 여부

 

[풀이]

- k번 동안 아래 과정 반복한다.

    0. 자료구조들을 초기화한다.

    1. map을 탐색하며 부서진 포합이 아니면 WEAKEST와 STRONGEST에 {공격력, 마지막 공격 시간, 행, 열}을 추가한다.

    2. WEAKEST에서 공격자, STRONGEST에서 공격 대상자를 추출한다.

        - 공격자와 공격 대상자가 같으면 다음 후보를 공격 대상자로 추출한다.

        - 공격 대상자가 null이면 더이상 공격을 진행할 포탑이 없으므로 반복을 종료한다.

    3. 공격자의 공격력에 n + m을 더하고, 마지막 공격 시간을 현재 시간으로 초기화한다.

        - 공격자와 공격 대상자의 좌표에 대해 isRelated를 true로 초기화한다.

    4. 레이저 공격이 가능한지 파악한다.

        - 레이저 공격이 가능하면 공격 대상자는 공격자의 공격력만큼, 최단 거리 경로에 위치한 포탑들은 (공격자의 공격력 / 2)만큼 공격력을 감소시킨다.

            - 다익스트라 알고리즘을 사용해 공격자부터 공격대상자까지 도착하면 레이저 공격 가능으로 판단, 그렇지 않으면 불가능으로 판단

        - 레이저 공격이 불가능하면 포탄 공격을 수행한다.

            - 공격 대상자는 공격자의 공격력만큼, 공격 대상자의 8방에 위치한 포탑들은 (공격자의 공격력 / 2)만큼 공격력을 감소시킨다.

    5. 부숴진 포탑이 아니고, 공격자, 공격 대상자, 공격관련자들이 아니면 공격력을 1씩 증가시킨다.

- k번 반복이 끝나면 남은 포탑 중 가장 큰 공격력을 출력한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static final int[][] DELTAS_FOR_ATTACK1 = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static final int[][] DELTAS_FOR_ATTACK2 = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    private static final int X = 2;
    private static final int Y = 3;
    private static final int POWER = 0;
    private static final int LAST_ATTACK = 1;
    private static final int BROKEN = 0;
    private static final int DISTANCE = 2;
    private static final int DIRECTION = 3;
    private static final PriorityQueue<int[]> WEAKEST = new PriorityQueue<>((t1, t2) -> {
        if (t1[POWER] == t2[POWER]) {
            if (t1[LAST_ATTACK] == t2[LAST_ATTACK]) {
                if ((t1[X] + t1[Y]) == (t2[X] + t2[Y])) {
                    return t2[Y] - t1[Y];
                }
                return (t2[X] + t2[Y]) - (t1[X] + t1[Y]);
            }
            return t2[LAST_ATTACK] - t1[LAST_ATTACK];
        }
        return t1[POWER] - t2[POWER];
    });
    private static final PriorityQueue<int[]> STRONGEST = new PriorityQueue<>((t1, t2) -> {
        if (t1[POWER] == t2[POWER]) {
            if (t1[LAST_ATTACK] == t2[LAST_ATTACK]) {
                if (t1[X] + t1[Y] == t2[X] + t2[Y]) {
                    return t1[Y] - t2[Y];
                }
                return (t1[X] + t1[Y]) - (t2[X] + t2[Y]);
            }
            return t1[LAST_ATTACK] - t2[LAST_ATTACK];
        }
        return t2[POWER] - t1[POWER];
    });
    private static final PriorityQueue<int[]> MOVES = new PriorityQueue<>((m1, m2) -> {
        if (m1[DISTANCE] == m2[DISTANCE]) {
            return m1[DIRECTION] - m2[DIRECTION];
        }
        return m1[DISTANCE] - m2[DISTANCE];
    });

    private static int n;
    private static int m;
    private static int[][][] map;
    private static int[][] distances;
    private static boolean[][] isVisited;
    private static boolean[][] isRelated;
    private static int[][][] roots;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        n = Integer.parseInt(stringTokenizer.nextToken());
        m = Integer.parseInt(stringTokenizer.nextToken());
        int k = Integer.parseInt(stringTokenizer.nextToken());
        map = new int[n][m][2];
        distances = new int[n][m];
        isVisited = new boolean[n][m];
        isRelated = new boolean[n][m];
        roots = new int[n][m][2];
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j][POWER] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }
        int time = 1;
        while (time <= k) {
            init();
            addTopInfos();
            int[] attacker = WEAKEST.poll();
            int[] target = STRONGEST.poll();
            if (attacker[X] == target[X] && attacker[Y] == target[Y]) {
                target = STRONGEST.poll();
            }
            if (target == null) {
                break;
            }
            attacker[POWER] += n + m;
            map[attacker[X]][attacker[Y]][POWER] = attacker[POWER];
            map[attacker[X]][attacker[Y]][LAST_ATTACK] = time;
            isRelated[attacker[X]][attacker[Y]] = true;
            isRelated[target[X]][target[Y]] = true;
            if (!findTargetByAttack1(attacker, target)) {
                attack2(attacker, target);
            }
            increasePower();
            time++;
        }
        System.out.println(getMaxPower());
    }

    private static void init() {
        WEAKEST.clear();
        STRONGEST.clear();
        MOVES.clear();
        for (int i = 0; i < n; i++) {
            Arrays.fill(isVisited[i], false);
            Arrays.fill(isRelated[i], false);
            Arrays.fill(distances[i], Integer.MAX_VALUE);
            for (int j = 0; j < m; j++) {
                Arrays.fill(roots[i][j], 0);
            }
        }
    }

    private static void addTopInfos() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j][POWER] != BROKEN) {
                    WEAKEST.offer(new int[]{map[i][j][POWER], map[i][j][LAST_ATTACK], i, j});
                    STRONGEST.offer(new int[]{map[i][j][POWER], map[i][j][LAST_ATTACK], i, j});
                }
            }
        }
    }

    private static boolean findTargetByAttack1(int[] attacker, int[] target) {
        MOVES.offer(new int[]{attacker[X], attacker[Y], 0, 0});
        distances[attacker[X]][attacker[Y]] = 0;
        while (!MOVES.isEmpty()) {
            int[] current = MOVES.poll();
            int x = current[0];
            int y = current[1];
            int distance = current[DISTANCE];
            if (x == target[X] && y == target[Y]) {
                attack1(attacker, target);
                return true;
            }
            if (isVisited[x][y]) {
                continue;
            }
            isVisited[x][y] = true;
            for (int direction = 0; direction < 4; direction++) {
                int dx = (x + DELTAS_FOR_ATTACK1[direction][0] + n) % n;
                int dy = (y + DELTAS_FOR_ATTACK1[direction][1] + m) % m;
                if (map[dx][dy][POWER] != BROKEN && !isVisited[dx][dy] && distances[dx][dy] > distance + 1) {
                    roots[dx][dy][0] = x;
                    roots[dx][dy][1] = y;
                    distances[dx][dy] = distance + 1;
                    MOVES.offer(new int[]{dx, dy, distance + 1, current[DIRECTION] * 10 + direction});
                }
            }
        }
        return false;
    }

    private static void attack1(int[] attacker, int[] target) {
        int attack = attacker[POWER];
        map[target[X]][target[Y]][POWER] -= attack;
        checkBroken(target[X], target[Y]);
        attack /= 2;
        int x = roots[target[X]][target[Y]][0];
        int y = roots[target[X]][target[Y]][1];
        while (x != attacker[X] || y != attacker[Y]) {
            isRelated[x][y] = true;
            map[x][y][POWER] -= attack;
            checkBroken(x, y);
            int nextX = roots[x][y][0];
            int nextY = roots[x][y][1];
            x = nextX;
            y = nextY;
        }
    }

    private static void attack2(int[] attacker, int[] target) {
        int attack = attacker[POWER];
        map[target[X]][target[Y]][POWER] -= attack;
        checkBroken(target[X], target[Y]);
        attack /= 2;
        int x = target[X];
        int y = target[Y];
        for (int[] delta : DELTAS_FOR_ATTACK2) {
            int dx = (x + delta[0] + n) % n;
            int dy = (y + delta[1] + m) % m;
            if ((dx != attacker[X] || dy != attacker[Y]) && map[dx][dy][POWER] != BROKEN) {
                map[dx][dy][POWER] -= attack;
                checkBroken(dx, dy);
                isRelated[dx][dy] = true;
            }
        }
    }

    private static void checkBroken(int x, int y) {
        if (map[x][y][POWER] < 0) {
            map[x][y][POWER] = 0;
        }
    }

    private static void increasePower() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j][POWER] != BROKEN && !isRelated[i][j]) {
                    map[i][j][POWER]++;
                }
            }
        }
    }

    private static int getMaxPower() {
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                max = Math.max(max, map[i][j][POWER]);
            }
        }
        return max;
    }
}