boj 17135 캐슬 디펜스

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

알고리즘 분류는 bfs지만 조합 + 정렬 + 시뮬레이션 + 구현 등 사용해야할 기법이 많았습니다.

 

제가 처음 접근한 방법은

우선 조합으로 궁수가 있을 자리를 모두 구해준 다음

bfs로 4방향 탐색하여 공격가능한 적을 모두 담아놓고 정렬하여 맨 첫번째에 있는 적만 제거하였고

그 다음 적들을 모두 아래로 내려 다음 bfs탐색을 하는 방식이었습니다.

 

위의 방법으로 AC를 받았지만 시간적인 손해가 많다는 생각이 들었고, 시간을 줄이기위해 다른 방법을 생각하였습니다.

 

궁수는 항상 N + 1번째 행에 있기때문에 밑을 볼 필요가 없습니다. 그래서 왼쪽, 위, 오른쪽만 탐색하면 됩니다.

여기서 문제 조건을 보시면 가장 가까운 적이 여러명이면 가장 왼쪽에 있는 적을 공격한다고 나와있습니다.

위의 조건에서 왼쪽 -> 위 -> 오른쪽 방향 순서로 탐색하면 무조건 공격해야할 대상을 먼저 찾는다는 결론이 나왔습니다. 이제 정렬은 사용하지 않아도됩니다.

 

그 다음 여러명의 궁수가 한명의 적을 공격할 수 있기때문에 궁수가 공격할 대상을 찾으면

boolean배열을 사용하여 true로 바꿔주었고, 이중 for문으로 true인 좌표의 list를 0으로 바꿔주었지만

int배열을 사용하여 모든 좌표를 다 넣어주었고, 하나의 for문으로 해결할 수 있었습니다.

 

마지막으로 적을 제거하고 난 후에 이중 for문을 돌려서 적이 모두 제거되었는지 확인하였습니다.

제거되었으면 break를 해주고, 아니면 적들을 아래로 내려야합니다.

하지만 저는 적들을 아래로 내리는것보다 궁수를 위로 올리는 것이 시간상 효율적이라는 것을 깨닫고 궁수를 위로 올리기 위해 n--를 하였습니다.

 

최종적으로 저의 로직은 이렇습니다.

1. 조합으로 궁수를 배치

2. bfs로 3방향 탐색하여 공격할 수 있는 적을 탐색 (적을 찾거나 D보다 거리가 커지면 break)

3. 2번에서 찾은 적 제거

4. 적이 모두 제거되었는지 확인

5. 적이 모두 제거되었으면 break, 아니면 궁수 한 칸 위로 이동(n--)

 

자바에서 Collection사용이 많아지면 시간적으로 비효율적이라고 생각해서 배열을 최대한 사용하였습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static boolean visit[][];
    static int direct[][] = { { 0, -1 }, { -1, 0 }, { 0, 1 } };
    static int list[][], copylist[][], attacker[], rkill[][];
    static int N, M, D, ans, kidx;
 
    static void bfs() {
        int n = N;
        int sum = 0;
        Deque<int[]> dq = new ArrayDeque<int[]>();
        ArrayList<int[]> kill = new ArrayList<>();
        while (true) {
            for (int k = 0; k < 3; k++) {
                dq.addLast(new int[] { n, attacker[k], 0 });
                for (int i = 0; i < n; i++)
                    Arrays.fill(visit[i], false);
 
                while (!dq.isEmpty()) {
                    int x = dq.peekFirst()[0];
                    int y = dq.peekFirst()[1];
                    int cnt = dq.pollFirst()[2];
 
                    if (cnt == D) {
                        dq.clear();
                        break;
                    }
                    boolean chk = false;
                    for (int i = 0; i < 3; i++) {
                        int nx = x + direct[i][0];
                        int ny = y + direct[i][1];
 
                        if (nx < 0 || ny < 0 || nx >= n || ny >= M)
                            continue;
                        if (visit[nx][ny])
                            continue;
                        if (copylist[nx][ny] == 1) {
                            chk = true;
                            kill.add(new int[] { nx, ny, cnt + 1 });
                            break;
                        } else {
                            dq.addLast(new int[] { nx, ny, cnt + 1 });
                            visit[nx][ny] = true;
                        }
                    }
                    if (chk)
                        break;
                }
                dq.clear();
 
                if (kill.isEmpty())
                    continue;
 
                rkill[kidx][0] = kill.get(0)[0];
                rkill[kidx++][1] = kill.get(0)[1];
                kill.clear();
            }
 
            for (int i = 0; i < kidx; i++) {
                if (copylist[rkill[i][0]][rkill[i][1]] == 1) {
                    copylist[rkill[i][0]][rkill[i][1]] = 0;
                    sum++;
                }
            }
            kidx = 0;
 
            boolean allkill = false;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < M; j++) {
                    if (copylist[i][j] == 1) {
                        allkill = true;
                        break;
                    }
                }
                if (allkill)
                    break;
            }
            if (!allkill)
                break;
            n--;
        }
 
        ans = Math.max(ans, sum);
    }
 
    static void func(int idx, int cnt) {
        if (cnt == 3) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++)
                    copylist[i][j] = list[i][j];
            }
            bfs();
            return;
        }
 
        for (int i = idx; i < M; i++) {
            attacker[cnt] = i;
            func(i + 1, cnt + 1);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        list = new int[N][M];
        copylist = new int[N][M];
        attacker = new int[3];
        visit = new boolean[N][M];
        rkill = new int[226][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
        System.out.println(ans);
    }
}