[JavaScript] 백준 골드 3 : 17135 - 캐슬 디펜스

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

---

📌 작성한 코드 

// 17135
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m, d] = input.shift().split(" ").map(Number);
const board = input.map((str) => str.split(" ").map(Number));

const duplicated = input.map((str) => str.split(" ").map(Number));

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const down = () => {
    board.pop();
    board.unshift(Array(m).fill(0));
};

const bfs = (a, b) => {
    const queue = [];
    queue.push([a, b, 1]);
    const visited = Array.from({ length: n }, () => new Array(m).fill(false));
    visited[a][b] = true;

    let min = Infinity;

    const attack = [];
    if (board[a][b] === 1) {
        return [a, b, 1];
    }

    let idx = 0;
    while (queue.length > idx) {
        const [x, y, count] = queue[idx++];
        if (count >= d) continue;

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny, count + 1]);

                if (board[nx][ny] === 1) {
                    if (count + 1 <= min) {
                        min = count + 1;
                        attack.push([nx, ny, count + 1]);
                    }
                }
            }
            if (count + 1 > d) break;
        }
    }

    attack.sort((a, b) => a[2] - b[2] || a[1] - b[1]);

    return attack[0];
};

let combi = Array(m).fill(false);

const combination = (at, count) => {
    if (count === 3) {
        main();
        return;
    }

    for (let i = at; i < m; i++) {
        if (!combi[i]) {
            combi[i] = true;
            combination(i + 1, count + 1);
            combi[i] = false;
        }
    }
};

let total = 0;

const main = () => {
    let answer = 0;

    for (let i = 0; i < n; i++) {
        const temp = new Set();
        for (let j = 0; j < m; j++) {
            if (!combi[j]) continue;
            const val = bfs(n - 1, j);

            if (!val) continue;
            const [x, y, count] = val;
            if (board[x][y] === 1) {
                temp.add(`${x},${y}`);
            }
        }

        [...temp].forEach((str) => {
            const [x, y] = str.split(",").map(Number);
            board[x][y] = 0;
        });
        answer += temp.size;

        down();
    }

    total = Math.max(total, answer);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            board[i][j] = duplicated[i][j];
        }
    }
};

combination(0, 0);
console.log(total);

 

📌 설명 

캐슬 디펜스 문제는 지문이 제시하는대로 배열의 값을 변경시키는 시뮬레이션(구현) 문제이다. 

게임 중 궁수의 공격을 죽일 수 있는 적의 최대 수를 구하면 된다. 

 

캐슬 디펜스 게임 진행 순서

1. N * M의 게임판이 있고, N + 1 번째 행에는 성이 존재한다. 3개의 성에 한명씩 궁수를 배치할 수 있다.

2. 각 턴마다 궁수는 공격 거리 D 이하에 있는 적 한명을 공격한다. 모든 궁수는 동시에 공격하기 때문에 같은 적을 공격할 수도 있다.

3. D거리 이하에 여러명의 적이 존재한다면 (1) 거리가 가장 짧은 적 (2) 가장 왼쪽에 존재하는 적 이라는 우선순위에 따라 공격한다. 

4. 공격이 끝난 이후에 적은 한 칸 아래로 이동한다.

4. 모든 적이 격자 판에서 제외되면 게임을 종료한다.

 

캐슬 디펜스 문제를 풀기 위해서 필요한 함수

1. combination : N개의 성 중에서 3개만 선택하는 조합을 구할 함수를 구현해야 한다. -> 필자는 백트래킹을 이용해서 구현하였다.

2. main : 매 턴 당 적을 공격하는 로직과 게임이 종료되면 변경된 격자판을 처음의 상태로 되돌리는 함수를 구현해야 한다. 

3. bfs : 현재 궁수의 위치에서 D 거리 이하에 있는 적을 구하고 우선순위에 따라 공격할 적을 선택하는 함수를 구현해야 한다.

4. down : 턴이 끝난 이후에 적을 한 칸 아래로 내려줄 함수를 구현해야 한다.

---

1. combination

- 백트래킹으로 3개를 선택하는 조합을 구현하고, 3개가 선택되면 main을 호출해서 게임을 진행하는 로직을 진행시킨다. 

let combi = Array(m).fill(false);

const combination = (at, count) => {
    if (count === 3) {
        main();
        return;
    }

    for (let i = at; i < m; i++) {
        if (!combi[i]) {
            combi[i] = true;
            combination(i + 1, count + 1);
            combi[i] = false;
        }
    }
};

2. main

- 선택된 궁수의 위치를 가지고 게임(궁수의 공격 -> 적의 내려옴)을 진행한다.

-> 각 궁수가 중복된 적을 공격할 수 있기 때문에 set을 사용해서 중복을 걸러준다. 배열로 저장하면 set이 작동하지 않으니 문자열로 저장한다.

-> 턴이 끝난 이후에 중복을 거른 적을 공격한다. (0으로 변경한다.)

-> 제거 가능한 최대 적을 구하는 것이 최종 목표이므로 사라진 적의 명수를 기록한다.

 

- 게임이 끝난 이후에는 게임판을 원래대로 돌려놓는다. 

-> 그리고 이번 판에서 죽인 적의 수와 최대값을 비교해서 업데이트 한다. 

const main = () => {
    let answer = 0;

    for (let i = 0; i < n; i++) {
        const temp = new Set();
        for (let j = 0; j < m; j++) {
            if (!combi[j]) continue;
            const val = bfs(n - 1, j);

            if (!val) continue;
            const [x, y, count] = val;
            if (board[x][y] === 1) {
                temp.add(`${x},${y}`);
            }
        }

        [...temp].forEach((str) => {
            const [x, y] = str.split(",").map(Number);
            board[x][y] = 0;
        });
        answer += temp.size;

        down();
    }

    total = Math.max(total, answer);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            board[i][j] = duplicated[i][j];
        }
    }
};

 

3. bfs 

- bfs를 이용해서 거리 d 이내에 있는 적을 찾는다. -> 저장된 적의 최소 거리 값(min)보다 적으면 현재 값을 min값으로 설정하고 저장한다. 

- 찾은 적들 중에서 우선 순위에 따라 정렬하고, 정렬한 값중 가장 작은 값을 반환한다.

const bfs = (a, b) => {
    const queue = [];
    queue.push([a, b, 1]);
    const visited = Array.from({ length: n }, () => new Array(m).fill(false));
    visited[a][b] = true;

    let min = Infinity;

    const attack = [];
    if (board[a][b] === 1) {
        return [a, b, 1];
    }

    let idx = 0;
    while (queue.length > idx) {
        const [x, y, count] = queue[idx++];
        if (count >= d) continue;

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny, count + 1]);

                if (board[nx][ny] === 1) {
                    if (count + 1 <= min) {
                        min = count + 1;
                        attack.push([nx, ny, count + 1]);
                    }
                }
            }
            if (count + 1 > d) break;
        }
    }

    attack.sort((a, b) => a[2] - b[2] || a[1] - b[1]);

    return attack[0];
};

 

** 21% 에서 실패했습니다 뜨는 경우 주목!

- d 넘어갔을 때 무시하는 로직 적어주지 않아서 생기는 문제이다. 꼭 추가해주도록 하자!

if (count >= d) continue;

 

4. down

- 한 칸 밑으로 내리기 == 맨 마지막 배열 삭제하기 

const down = () => {
    board.pop();
    board.unshift(Array(m).fill(0));
};

 

✅ 성공