[백준 17135] 캐슬디펜스 -JAVA // le_effort//

캐슬 디펜스

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	10708	3604	2041	29.149%

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

예제 입력 1

xxxxxxxxxx
5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

예제 출력 1

xxxxxxxxxx
3

예제 입력 2

xxxxxxxxxx
5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

예제 출력 2

xxxxxxxxxx
3

예제 입력 3

xxxxxxxxxx
5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

예제 출력 3

xxxxxxxxxx
5

예제 입력 4

xxxxxxxxxx
5 5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

예제 출력 4

xxxxxxxxxx
15

예제 입력 5

xxxxxxxxxx
6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

예제 출력 5

xxxxxxxxxx
9

예제 입력 6

xxxxxxxxxx
6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

예제 출력 6

14

 

사용 알고리즘

조합 + 구현

 

 

풀이

dfs를 이용한 조합으로 궁수의 위치를 뽑고 시작한다.

병사들이 내려 올 수 도 있지만 나는 궁수들을 한 칸씩 위로 올리는 풀이로 했다.

궁수의 x좌표가 0에 온다면 끝나는 것으로 구현했다.

 

궁수의 위치 기준으로 한칸위 부터 탐색을 진행하며 거리가 같은 경우 왼쪽에 있는것으로 초기화 해주고 거리가 더 작으면 바꿔주면 된다.

주의 할 점은 궁수가 여러명의 적을 동시에 사격 할 수 있으니 리스트에 담아두고 3명의 궁수가 다 사격을 마친 후에 적을 없애주고 cnt를 올려준다.

 

전체 코드중 tmp_x와 tmp_y를 100으로 둔 건

맵의 크기상 100,100 이 절대 나올수 없어서 두었다

import java.io.*;
import java.util.*;
public class Main {
    static int n,m,d;
    static int map[][];
    static boolean visited[];
    static int arr[];
    static int cnt=0;
    static int pos;
    static int max=-1;
    static int copy_map[][];
    static ArrayList<Node>enemy = new ArrayList<>();
    static Queue<Node>q = new LinkedList<>();   //궁수들의 위치
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        d = Integer.parseInt(t[2]);
        map = new int[n+1][m];
        copy_map = new int[n+1][m];
        visited = new boolean[m];
        arr = new int[3];
        for(int i=0; i<n; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        dfs(0,0);
        System.out.println(max);
    }
    public static void copy() {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
    }
    public static void dfs(int start,int level) {
        if(level==3) {
            copy();
            q.clear();
            for(int i=0; i<3; i++) {
                q.add(new Node(n,arr[i]));
            }
            cnt =0;
            pos = n;
            solve();
            return;
        }
        for(int i=start; i<m; i++) {
            if(!visited[i]) {
                arr[level]=i;
                visited[i]=true;
                dfs(i+1,level+1);
                visited[i] = false;
            }
        }
    }
    public static void solve() {
        while(pos !=0) {
            enemy.clear();
            for(int i=0; i<3; i++) {
                Node solider = q.poll();
                int x = solider.x;
                int y = solider.y;
                int tmp_x=100;
                int tmp_y=100;
                int tmp_d=d;
                
                for(int j=x-1; j>=0; j--) {
                    for(int k=0; k<m; k++) {
                        if(copy_map[j][k]==1 && Math.abs(x-j)+Math.abs(y-k)<=tmp_d) {
                            if(tmp_d == Math.abs(x-j)+Math.abs(y-k)) {  // 거리가 같을때  가장 왼쪽 
                                if(tmp_y>k) {
                                    tmp_x=j;
                                    tmp_y=k;
                                }
                            }
                            
                            else {  //if 문에 의해서 거리가 같은게 걸러지므로  최소거리
                                tmp_d = Math.abs(x-j)+Math.abs(y-k);
                                tmp_x=j;
                                tmp_y=k;
                            }
                        }
                    }
                }
                q.add(new Node(x-1,y));
                if(tmp_x !=100 && tmp_y !=100) {
                    enemy.add(new Node(tmp_x,tmp_y));
                }
            }
            for(int i=0; i<enemy.size(); i++) {
                if(copy_map[enemy.get(i).x][enemy.get(i).y]==1) {
                    copy_map[enemy.get(i).x][enemy.get(i).y]=0;
                    cnt++;
                }
            }
            pos--;
        }
        max = Math.max(max, cnt);
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}