[BOJ-17135][시뮬레이션/조합] 캐슬 디펜스 - Java

문제 바로가기

17135번: 캐슬 디펜스

삼성 SW 역량테스트 A형 기출문제입니다. 구현이 쪼오오금 까다로운 시뮬레이션 문제입니다. 궁수가 쏴죽이는 적들의 최대를 구하면 됩니다.

import java.io.*;
import java.util.*;

class Dir{
    int y, x;
    Dir(int y, int x){
        this.y = y; this.x = x;
    }
}

public class Main {
    static int N, M, D;
    static int[][] map;
    static int ans = 0;
    static int enemy = 0;

    public static int dist(Dir a, Dir e) {
        return Math.abs(a.y - e.y) + Math.abs(a.x - e.x);
    }

    public static int attack() {
        int tEnemy = enemy;
        int cnt = 0;
        int[][] tempMap = new int[N+1][M];
        for(int i = 0; i <= N; i++)
            System.arraycopy(map[i], 0, tempMap[i], 0, map[i].length);

        ArrayList<Dir> archers = new ArrayList<>();
        for(int i =0 ; i<M; i++) {
            if(map[N][i] == 2) archers.add(new Dir(N, i));
            if(archers.size() == 3) break;
        }

        while(tEnemy > 0) {
            ArrayList<Dir> minDir = new ArrayList<Dir>();

            for(int a = 0; a < 3; a++ ) {
                int minDist = 99999;
                minDir.add(new Dir(N, 0));
                for(int j = 0; j< M; j++) {
                    for(int i = N-1; i>= 0; i--) {
                        if(tempMap[i][j] == 1) {
                            int distance = dist(archers.get(a), new Dir(i, j));
                            if(distance > D) continue;
                            if(minDist > distance) {
                                minDist = distance;
                                minDir.get(a).y = i; minDir.get(a).x = j;
                            }
                        }
                    }
                }        
            }

            for(int i = 0; i<minDir.size(); i++) {
                if(minDir.get(i).y == N || tempMap[minDir.get(i).y][minDir.get(i).x] == 0) continue;
                tempMap[minDir.get(i).y][minDir.get(i).x] = 0;
                cnt++;
                tEnemy--;
            }

            for(int i = 0; i< M; i++) if(tempMap[N-1][i] == 1) tEnemy--;
            for(int i = N-1; i>=0; i--) {
                for(int j = 0; j< M; j++) { 
                    if(i == 0) tempMap[i][j] = 0;
                    else tempMap[i][j] = tempMap[i-1][j];
                }
            }
        }
        return cnt;
    }

    public static void makeArcher(int cnt, int start) {
        if(cnt == 3) {
            int ret = attack();
            ans = ans > ret ? ans : ret;
            return;
        }

        for(int i = start; i < M; i++) {
            map[N][i] = 2;
            makeArcher(cnt+1, i+1);
            map[N][i] = 0;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        map = new int[N+1][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) enemy++;
            }
        }

        makeArcher(0, 0);

        System.out.println(ans);
    }
}

우선 궁수는 최대 3명을 둘 수 있기 때문에 조합으로 궁수를 놔줍니다. mC3 이요.

궁수들은 거리 D 이하에 있는 적만 쏠 수 있는데, 이때 N과 M의 최대값이 15이므로 2중 for문으로 봐줘도 되고 BFS를 써서 봐줘도 됩니다.

 

//BFS로 탐색
while(!q.empty()){
    int cx = q.front().first;
    int cy = q.front().second;q.pop();
    for(int i = 0;i < 3;i++) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];

        if (!isIn(nx, ny) || nx == N) continue;
        if (c[nx][ny]) continue;
        if (c[cx][cy] > D) continue;
        c[nx][ny] = c[cx][cy] + 1;
        q.push({ nx, ny });
        if (tMap[nx][ny] == 1 && c[nx][ny] <= D + 1) {
            if (c[nx][ny] < minDist) {
                minDist = c[nx][ny];
            }
        }
    }
}

같은 거리에 있는 적이라면 왼쪽에 있는 적을 공격해야 하므로 그냥 왼쪽부터 봐주면 됩니당.

 

자바에서 2차원 배열 복사하기

int[][] arry1;
int[][] arry2;
for(int i = 0; i <= arry1.length; i++)
	System.arraycopy(arry1[i], 0, arry2[i], 0, arry1[i].length);
  //System.arraycopy(src, srcPos, dest, destPos, length);