[BOJ] 17135 캐슬 디펜스 - JAVA

ONE·2021년 11월 24일
2

Baekjoon Online Judge

목록 보기
6/16

📚 Problem

17135 캐슬 디펜스

📝 Solution

  • 거리가 D 이하인 적중에서 가장 가까운 적을 공격
  • 만약 위의 경우가 여럿일 경우, 가장 왼쪽의 적을 공격
  • 여러명의 궁수에게 공격 당하는 것이 가능
  • 궁수의 자리가 1 ~ M 중에서 3개를 뽑는 조합 문제
  • 궁수의 공격으로 제외되는 적 의 최대수 구하기
  • 궁수의 위치를 저장한 객체배열을 이용해 반복문을 돌립니다
  • 거리가 가장 가까운 적을 찾아야 하기때문에, 적이 있으면 거리를 비교하여 더 적은 거리라면 최소 거리의 적의 위치를 갱신합니다
  • 만약 같은거리라면 열의 값을 비교하여 더 왼쪽의 위치를 선택하여 갱신합니다
  • 가장 가까운 적의 위치를 찾은 후 거리가 D 이하라면 indexToKill 의 배열의 위치를 true로 바꿔줍니다
  • 적을 공격하고 바로 0 으로 안바꾸는 것은 한명의 적을 여러 궁수가 공격할 수 있기 때문에
  • 먼저 indexToKill 배열에서 위치만 지정하고 이후에 배열의 값을 0으로 바꿔주고 궁수에게 공격당한 적의 수를 카운트합니다
            for(Node archer : archers){
                Node enemy = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
                int enemyD = Integer.MAX_VALUE;

                for(int i = 1; i <= N; i++)
                    for(int j = 1; j <= M; j++)
                        if(copiedGame[i][j] == 1){
                            if(enemyD > enemyDistance(archer, i, j)){
                                enemy.r = i;
                                enemy.c = j;
                                enemyD = enemyDistance(archer, i, j);
                            }
                            if(enemyD == enemyDistance(archer, i, j))
                                if(enemy.c > j){
                                    enemy.r = i;
                                    enemy.c = j;
                                }
                        }
                if(enemyD <= D)
                    indexToKill[enemy.r][enemy.c] = true;
            }
  • 조합을 이용하여 M개의 자리중에서 3자리를 뽑는 것DFS 로 구현
  • 인덱스 3개를 뽑은 후 game 배열을 복사하여 N + 1 행에
  • 해당 인덱스 3개에 궁수를 -1의 값으로 넣어준다
    private static void DFS(int depth){
        if(depth == 3){
            int[][] tmpGame = copyGame();
            for(int index : order)
                tmpGame[N + 1][index] = -1;
            play(tmpGame);
            return;
        }
        for(int i = 1; i <= M; i++)
            if(!visited[i]){
                visited[i] = true;
                order[depth] = i;
                DFS(depth + 1);
                visited[i] = false;
            }
    }

💻 Code

import java.util.Scanner;

class Node{
    int r;
    int c;

    public Node(int r, int c){
        this.r = r;
        this.c = c;
    }
}

public class Main {
    private static int N, M, D, max;
    private static int[] archer;
    private static int[] order;
    private static boolean[] visited;
    private static int[][] game;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();
        D = scanner.nextInt();

        order = new int[3];
        visited = new boolean[M + 1];
        archer = new int[M + 1];
        for(int i = 1; i <= M; i++)
            archer[i] = i;

        game = new int[N + 2][M + 1];
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                game[i][j] = scanner.nextInt();

        DFS(0);

        System.out.println(max);

        scanner.close();
    }

    private static int[][] copyGame(){
        int[][] tmpGame = new int[N + 2][M + 1];
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                tmpGame[i][j] = game[i][j];
        return tmpGame;
    }

    private static boolean isAllDead(int[][] copiedGame){
        boolean check = true;
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                if(copiedGame[i][j] == 1){
                    check = false;
                    break;
                }
        return check;
    }

    private static void moveEnemies(int[][] copiedGame){
        for(int i = N; i >= 1; i--)
            for(int j = 1; j <= M; j++)
                if(copiedGame[i][j] == 1){
                    if(i == N)
                        copiedGame[i][j] = 0;
                    else{
                        copiedGame[i][j] = 0;
                        copiedGame[i + 1][j] = 1;
                    }
                }
    }

    private static int enemyDistance(Node archer, int x, int y){
        return Math.abs(archer.r - x) + Math.abs(archer.c - y);
    }

    private static void play(int[][] copiedGame){
        int killByArcher = 0;
        Node[] archers = new Node[3];

        int index = 0;
        for(int j = 1; j <= M; j++)
            if(copiedGame[N + 1][j] == -1)
                archers[index++] = new Node(N + 1, j);

        while (!isAllDead(copiedGame)) {
            boolean[][] indexToKill = new boolean[N + 1][M + 1];

            for(Node archer : archers){
                Node enemy = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
                int enemyD = Integer.MAX_VALUE;

                for(int i = 1; i <= N; i++)
                    for(int j = 1; j <= M; j++)
                        if(copiedGame[i][j] == 1){
                            if(enemyD > enemyDistance(archer, i, j)){
                                enemy.r = i;
                                enemy.c = j;
                                enemyD = enemyDistance(archer, i, j);
                            }
                            if(enemyD == enemyDistance(archer, i, j))
                                if(enemy.c > j){
                                    enemy.r = i;
                                    enemy.c = j;
                                }
                        }
                if(enemyD <= D)
                    indexToKill[enemy.r][enemy.c] = true;
            }
            for(int i = 1; i <= N; i++)
                for(int j = 1; j <= M; j++)
                    if(indexToKill[i][j]){
                        copiedGame[i][j] = 0;
                        killByArcher++;
                    }
            moveEnemies(copiedGame);
        }
        max = Math.max(max, killByArcher);
    }

    private static void DFS(int depth){
        if(depth == 3){
            int[][] tmpGame = copyGame();
            for(int index : order)
                tmpGame[N + 1][index] = -1;
            play(tmpGame);
            return;
        }
        for(int i = 1; i <= M; i++)
            if(!visited[i]){
                visited[i] = true;
                order[depth] = i;
                DFS(depth + 1);
                visited[i] = false;
            }
    }
}
profile
New, Strange, Want to try

0개의 댓글