ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [BOJ] 캐슬디펜스
    Algorithm/BOJ 2020. 2. 13. 15:06

    [17135] 캐슬디펜스

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

    • 게임이 진행되는 곳은 크기가 NXM인 격자판이다.
    • 각 칸에 포함된 적의 수는 최대 하나이며, N+1행의 모든 칸에는 성이 있다.
    • 성을 적에게서 지키기 위해 성이 있는 칸(N+1)에 궁수 3명을 배치하려고 한다.
    • 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고 공격받은 적은 게임에서 제외된다.
    • 궁수의 공격이 끝나면, 적은 아래로 한 칸 이동하며 성이 있는 칸으로 내려간 경우에는 게임에서 제외된다.
    • 모든 적이 격자판에서 제외되면 게임이 끝난다.
    • 입력 :  N(행) M(열) D(거리 제한), NxM(격자판의 상태)
    • 출력 :  궁수의 공격으로 제거할 수 있는 적의 최대 수 

     

     

    Solution

    • permutation()으로 궁수의 자리를 바꿔가며 BFS로 궁수를 제거하였다.
    • 문제의 조건은 최대한 많은 적을 죽이는 것이지만 가장 가까운 적을 우선으로 죽여야 하는 것이다.
    • 세 명의 궁수가 동시에 죽일 수 있도록 구현하는 것이 중요하다.

     

     

    소스코드

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.StringTokenizer;
     
    public class Main {
        static int n, m, d, answer;
        static int[][] map, copy, visited;
        static int[] a;
        static int[] dx = { 0-10 };
        static int[] dy = { -101 };
        static Queue<Node> q;
     
        static class Node {
            int x, y, step;
     
            public Node(int x, int y, int step) {
                this.x = x;
                this.y = y;
                this.step = step;
            }
        }
     
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = stoi(st.nextToken());
            m = stoi(st.nextToken());
            d = stoi(st.nextToken());
     
            map = new int[n][m];
            
            
     
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < m; j++) {
                    map[i][j] = stoi(st.nextToken());
                }
            }
            answer = Integer.MIN_VALUE;
            a = new int[3];
            permutation(00);
            System.out.println(answer);
     
        }
     
        static void permutation(int depth, int start) {
            if (depth == 3) {
                
                simulation();
                return;
            }
     
            for (int i = start; i < m; i++) {
                a[depth] = i;
                permutation(depth + 1, i + 1);
            }
        }
     
        static void simulation() {
            copy();
            int count = 0;
            for (int j = 1; j <= n; j++) {
                for (int i = 0; i < a.length; i++) {
                    count += bfs(new Node(n + 1, a[i], 0));
                }
                
                move();
            }
     
            answer = Math.max(answer, count);
        }
     
        static int bfs(Node node) {
            q = new LinkedList<>();
            q.offer(node);
            visited = new int[n + 2][m];
            visited[node.x][node.y] = 1;
            while (!q.isEmpty()) {
                Node cur = q.poll();
                for (int i = 0; i < 3; i++) {
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];
     
                    if (nx < 1 || ny < 0 || nx >= n + 1 || ny >= m)
                        continue;
     
                    if(visited[nx][ny] == 1)
                        continue;
                    
                    if (copy[nx][ny] > 0 && cur.step < d) {
                        if(copy[nx][ny] == 1) {
                            copy[nx][ny] = 2;
                            return 1;
                        }else {
                            return 0;
                        }
                        
                    } else if (copy[nx][ny] == 0 && cur.step < d) {
                        q.offer(new Node(nx, ny, cur.step + 1));
                        visited[nx][ny] = 1;
     
                    }
                }
            }
            return 0;
        }
     
        static void move() {
            for (int i = n; i > 0; i--) {
                copy[i] = copy[i - 1];
                for (int j = 0; j < m; j++) {
                    if (copy[i][j] == 2)
                        copy[i][j] = 0;
                }
            }
        }
     
        static void copy() {
            copy = new int[n + 2][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    copy[i+1][j] = map[i][j];
                }
            }
        }
     
        static void print(int[][] a) {
            for (int i = 0; i < n + 2; i++) {
                for (int j = 0; j < m; j++) {
                    System.out.print(a[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("------------");
        }
     
        static void print(int[] a) {
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
     
        static int stoi(String s) {
            return Integer.parseInt(s);
        }
    }
    cs
     

    'Algorithm > BOJ' 카테고리의 다른 글

    [BOJ] 패션왕 신해빈  (0) 2020.05.27
    [BOJ] 연구소3  (0) 2020.04.28
    [BOJ] 배열 돌리기 3  (0) 2020.02.11
    [BOJ] 배열 돌리기 1  (0) 2020.02.10
    [BOJ] 게리멘더링  (0) 2020.02.10

    댓글

Designed by Tistory.