[백준]17135_캐슬디펜스

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

구현 문제인데 예전에 실패해서 오랜만에 도전해보았다.

아무래도 계속 알고리즘을 하니까 늘긴하나보다.

문제에서 적을 찾아내는 과정에서 가까운 오른쪽 우선순위의 적을 찾는 부분이
쉽게 떠오르지 않아서 많은 시간을 보냈지만, 순간 머리에 응? BFS..?가 떠올라서 손으로 직접 그리면서
풀이를 해보았는데, 아무래도 맞는것 같아서 도전했다!
다시한번 깨닫는 문제 정의와 풀이를 정하고 코드를 작성하는 습관!

다른사람 풀이도 궁금해서 염탐하거 가봅니다.

 

package BJ;

/**
 * 궁수가 갈 수 있는 모든위치의 조합을 구한 하여 조합 값으로 궁수 배치
 * 이후에, 시뮬레이션 돌린다.
 * <p>
 * 시뮬레이션
 * 3명 궁수 모두 현재 자리에서 가장 가깝고 왼쪽 우선으로 적을 고른다.
 * 공격할 대상을 isAttack에 기록한다.
 * 3명 모두 공격할 대성을 파악 후 tmpMap 복사한 맵에 죽은 적은 0으로 표시한다.
 * <p>
 * 가장 가까운 적 + 왼쪽 우선으로 찾기 (BFS)
 * 좌, 상, 우 -> 순으로 순회한다.
 * 큐에 미방문이고 공격 범위 내에 있는 위치만 삽입한다.
 * 방문한 현재 위치가 적이면 공격대상을 찾은것.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_17135_캐슬디펜스 {
    static int N, M, D, maxKill = 0, limit = 3;
    static int[][] gameMap, tmpMap;
    static int comResult[], v[][];
    static boolean[][] isAttack;

    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());


        gameMap = new int[N + 1][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                gameMap[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        comResult = new int[limit]; // 궁수는 3명만
        // 조합을 구해서 각 궁수 위치 조합에 따라 처치할 수 있는 적의 수를 받아온다.
        com(M, 3, 0, 0, 0);
        System.out.println(maxKill);
    }

    private static void com(int n, int r, int idx, int num, int selectCnt) {
        // 궁수 3명을 다 선택한 경우
        if (selectCnt == r) {
            int killCnt = 0;
            isAttack = new boolean[N][M]; // 공격받은 적을 기록
            tmpMap = copyGameMap();
            simulation(comResult); // 시뮬레이션 실행
            for (boolean[] booleans : isAttack) {
                for (boolean death : booleans) {
                    if (death) killCnt++;
                }
            }
            maxKill = Math.max(maxKill, killCnt);
            return;
        }

        // 현재 위치를 선택하지 않거나, 다음 위치로 이동하는 경우
        if (num < n) {
            comResult[idx] = num;
            com(n, r, idx + 1, num + 1, selectCnt + 1); // 선택한 경우
            com(n, r, idx, num + 1, selectCnt); // 미선택한 경우
        }
    }


    private static int[][] copyGameMap() {
        int[][] result = new int[gameMap.length][gameMap[0].length];
        for (int i = 0; i < gameMap.length; i++) {
            for (int j = 0; j < gameMap[0].length; j++) {
                result[i][j] = gameMap[i][j];
            }
        }
        return result;
    }

    // N-1번부터 올라가면서 탐색할거임
    private static void simulation(int[] comResult) {

        // 궁수들의 위치 기록.
        int[][] archers = new int[limit][2];
        for (int i = 0; i < N; i++) {
            // 편의상 궁수가 앞으로 이동한다.
            archers[0] = new int[]{N - i, comResult[0]};
            archers[1] = new int[]{N - i, comResult[1]};
            archers[2] = new int[]{N - i, comResult[2]};
            atteck(archers);
        }
    }

    private static void atteck(int[][] archers) {

        // 각 궁수가 자신과 가장 가까운 적을 찾아낸다.
        for (int i = 0; i < limit; i++) {
            // 각 궁수가 공격할 적을 선택 후 결과를 isAttack에 기록한다.
            bfs(archers[i]);
            // 편의상 궁수가 위치를 1칸 위로 이동한다.
        }

        for (int i = 0; i < isAttack.length; i++) {
            for (int j = 0; j < isAttack[0].length; j++) {
                if (isAttack[i][j]) { // 공격당한 적을 0으로 설정, 중복으로 공격하는걸 막기 위함.
                    tmpMap[i][j] = 0;
                }
            }
        }


    }

    /**
     *
     * @param archer 각 위치의 궁수기준
     *               가장 가까운적을 찾는다.
     */
    private static void bfs(int[] archer) {
        // 좌상우
        int[] dx = {0, -1, 0};
        int[] dy = {-1, 0, 1};
        Queue<int[]> q = new LinkedList<>();
        q.offer(archer);
        // 출발지.
        v = new int[N + 1][M]; // 궁수 위치만큼 행 생성.
        v[archer[0]][archer[1]] = 0; // 출발위치 초기화 : 현재 궁수 위치 기준으로 탐색.


        while (!q.isEmpty()) {
            int[] curArcher = q.poll();
            int ci = curArcher[0], cj = curArcher[1];

            // 가장 가까운 적 찾은경우.
            if (tmpMap[ci][cj] == 1) {
                isAttack[ci][cj] = true; // 공격대상으로 지정한다.
                return;
            }
            for (int dr = 0; dr < 3; dr++) {
                int ni = ci + dx[dr];
                int nj = cj + dy[dr];
                // 범위내, 미방문, 전방문+1<=D -> 궁수의 공격 범위내에 유효한 값만 큐에 넣음
                if (isIn(ni, nj, archer[0]) && v[ni][nj] == 0 && v[ci][cj] + 1 <= D) {
                    v[ni][nj] = v[ci][cj] + 1; // 거리를 표시하는 것.
                    q.offer(new int[]{ni, nj});
                }
            }
        }
    }

    /**
     *
     * @param ni
     * @param nj
     * @param limitRow 궁수의 행위치
     * @return 범위내에 궁수를 지나친 위치가 아닌경우
     */
    private static boolean isIn(int ni, int nj, int limitRow) {
        return 0 <= ni && ni < limitRow && 0 <= nj && nj < M;
    }
}