17135 캐슬 디펜스 ( 자바스크립트 )

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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명의 궁수가 위치 할 수 있는 조합을 구해본다.

const combinations = [];
const makeCombination = (arr, idx) => {
    if (arr.length === 3) {
        combinations.push(arr);
        return;
    }
	for (let i = idx + 1; i < m; i++) {
    	makeCombination([...arr, i], i);
	}
};
makeCombination([], -1);

이제 만들어진 궁수들의 위치 조합으로 각각의 게임을 진행해보면 된다.

for (const combi of combinations) {
        const game = gr.map((v) => [...v]);
		
        let enemy = 0;
		// ...생략 
        
        answer = Math.max(answer, enemy);
}

각각의 게임에서는 스테이지가 존재하며 몬스터들이 죄다 내려오면 게임이 끝나니까 stage는 n 번 진행하면 된다.

for (let stage = 0; stage < n; stage++) {
	// 게임 진행
	
	const pushArray = Array.from({ length: m }, () => 0);
	game.pop();
    game.unshift(pushArray);
}

각 스테이지마다 행이 하나씩 내려오니까 game은 pop이 되고 [0]*m 의 배열을 unshift 해주면 된다. (또는 궁수가 놓여있는 row를 한 줄 씩 올린다고 생각해도 좋다.)

각 게임에서 궁수는 자기에게 가장 가까운 몬스터를 공격할 수 있으며, 같은 거리에 있는 몬스터라면 가장 왼쪽의 몬스터만을 공격할 수 있다. 궁수의 위치에서 제일 먼저 공격하는 것은 (nx-1, y) 이다. 이 곳에 몬스터가 없다면 그 다음 순서는 

( nx-1, y-1 ) , (nx-2,y) , (nx-1,y+1) 이다. 이것을 dx,dy로 표현하면 아래와 같고,

큐에 담아주면서 검사를 진행한다. ( bfs 방식을 채택 ) 

const dx = [0, -1, 0];
const dy = [-1, 0, 1];
for (let i = 0; i < 3; i++) {
    const nx = cx + dx[i];
    const ny = cy + dy[i];
    if (nx < 0 || ny < 0 || ny >= m) continue;
    q.push([nx, ny, cnt + 1]);
}

여기에서 주의할 점은, 한 스테이지에서 여러 명의 궁수가 하나의 몬스터를 처리할 수 있다는 것이다.

그래서 나는 집합을 사용해주었다.

const v = new Set();
if (game[cx][cy] === 1) {
    v.add(cx * m + cy);
    break;
}

모든 궁수들이 한 스테이지에서 공격한 몬스터의 number가 중복 없이 들어갈테고 

스테이지가 끝날 때마다 지금까지 처리한 enemy에 v.size를 더해주고 game 판에서도 몬스터의 흔적을 지워준다.

for (const value of v) {
    const nn = Math.floor(value / m);
    const mm = value % m;
    game[nn][mm] = 0;
}
enemy += v.size;

이제 최대 enemy 값을 answer와 비교하면서 최댓값을 출력해준다.

정답 코드

const dx = [0, -1, 0];
const dy = [-1, 0, 1];
const main = (n, m, d, gr) => {
    const combinations = [];
    const makeCombination = (arr, idx) => {
        if (arr.length === 3) {
            combinations.push(arr);
            return;
        }
        for (let i = idx + 1; i < m; i++) {
            makeCombination([...arr, i], i);
        }
    };
    makeCombination([], -1);
    let answer = 0;

    for (const combi of combinations) {
        const game = gr.map((v) => [...v]);

        let enemy = 0;
        for (let stage = 0; stage < n; stage++) {
            const v = new Set();
            for (let y of combi) {
                const q = [[n - 1, y, 1]];
                while (q.length) {
                    const [cx, cy, cnt] = q.shift();
                    if (game[cx][cy] === 1) {
                        v.add(cx * m + cy);
                        break;
                    }
                    if (cnt >= d) continue;
                    for (let i = 0; i < 3; i++) {
                        const nx = cx + dx[i];
                        const ny = cy + dy[i];
                        if (nx < 0 || ny < 0 || ny >= m) continue;
                        q.push([nx, ny, cnt + 1]);
                    }
                }
            }
            for (const value of v) {
                const nn = Math.floor(value / m);
                const mm = value % m;
                game[nn][mm] = 0;
            }
            enemy += v.size;
            const pushArray = Array.from({ length: m }, () => 0);
            game.pop();
            game.unshift(pushArray);
        }
        answer = Math.max(answer, enemy);
    }
    console.log(answer);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m, d] = input[0].split(' ').map((v) => +v);
const gr = input.slice(1).map((v) => v.split(' ').map((v) => +v));
main(n, m, d, gr);