[BOJ] 캐슬디펜스

[17135] 캐슬디펜스

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

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

 

 

Solution

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

 

 

소스코드

 

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, -1, 0 };
    static int[] dy = { -1, 0, 1 };
    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(0, 0);
        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);
    }
}