백준 17135 : 캐슬 디펜스 - javascript(완전탐색, dfs, 시뮬레이션)

문제 출처 

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

 

정답 풀이 

 

• simulation 함수는 주어진 궁수 배치에서 적을 제거하는 과정을 시뮬레이션하고, 제거된 적의 수를 반환합니다.
• combination 함수는 M열 중에서 3개의 궁수 위치를 선택하는 모든 경우의 수를 계산합니다.
• simulation에서 궁수의 사정거리에 있는 적을 탐색하고, 가장 가까운 적을 우선순위에 따라 공격합니다.
• 시뮬레이션 결과를 바탕으로 궁수 배치 중 적을 가장 많이 제거할 수 있는 경우를 탐색합니다.

 

정답 코드 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M, D] = input.shift().split(' ').map(Number);
const map = input.map(line => line.split(' ').map(Number));
let answer = 0;

// 적 위치에 따라 시뮬레이션 실행
const simulation = (archers) => {
    let count = 0;
    const tempMap = map.map(row => [...row]); // 맵 복사

    const inRange = (x, y) => x >= 0 && y >= 0 && x < N && y < M;

    // 적 제거 시뮬레이션 실행
    for (let turn = 0; turn < N; turn++) {
        const targets = new Set(); // 이번 턴에 제거될 적들

        archers.forEach(archer => {
            let target = null;
            let minDist = D + 1;

            // 궁수가 사정거리 내에 있는 적을 찾음
            for (let i = 0; i < N; i++) {
                for (let j = 0; j < M; j++) {
                    if (tempMap[i][j] === 1) {
                        const dist = Math.abs(N - i) + Math.abs(archer - j);
                        if (dist <= D) {
                            if (dist < minDist || (dist === minDist && j < target[1])) {
                                target = [i, j];
                                minDist = dist;
                            }
                        }
                    }
                }
            }
            if (target) {
                targets.add(`${target[0]} ${target[1]}`);
            }
        });

        // 공격된 적 제거
        targets.forEach(target => {
            const [x, y] = target.split(' ').map(Number);
            if (tempMap[x][y] === 1) {
                count++;
                tempMap[x][y] = 0;
            }
        });

        // 적 이동
        tempMap.pop(); // 맨 아래 행 제거
        tempMap.unshift(new Array(M).fill(0)); // 새로운 행 추가
    }

    return count;
};

// 궁수 위치 선택 (조합)
const combination = (arr, selectNum) => {
    const results = [];
    if (selectNum === 1) return arr.map(value => [value]);
    arr.forEach((current, index) => {
        const smallerCombinations = combination(arr.slice(index + 1), selectNum - 1);
        smallerCombinations.forEach(smallerCombination => {
            results.push([current, ...smallerCombination]);
        });
    });
    return results;
};

// 궁수 배치 모든 경우 탐색
const archerPositions = combination(Array.from({ length: M }, (_, i) => i), 3);

archerPositions.forEach(archers => {
    const result = simulation(archers);
    answer = Math.max(answer, result);
});

console.log(answer);

내 풀이 코드 

- dfs 에서 궁수를 마지막 행에만 배치하는 완탐 실행

- possible() : 사정거리 내 가장 가까운 적 찾기 

- attack() : 궁수 공격 처리 

- remove() :  중복되지 않게 제거하기 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n, m, d] = input.shift().split(' ').map(v => +v); 
const graph = input.map(el => el.split(' ').map(v => +v)); 

let max = 0;

// 궁수를 마지막 행에 배치 (DFS로 모든 경우의 수 탐색)
function dfs(arrow, idx) {
    if (arrow.length === 3) {
        const map = graph.map(el => el.slice()); // 맵 복사
        let result = attack(arrow, map); // 공격 시뮬레이션
        max = Math.max(max, result);
        return; 
    }
    for (let i = idx; i < m; i++) {
        arrow.push(i);
        dfs(arrow, i + 1);
        arrow.pop();
    }
}

// 공격 로직
function attack(archers, map) {
    let time = n; 
    let count = 0;

    while (time > 0) {
        let targets = new Set(); // 이번 턴에 제거될 적들

        // 각 궁수가 공격할 적 찾기
        archers.forEach(col => {
            let target = possible(n, col, map); // 궁수의 위치는 항상 마지막 행 (n)
            if (target[0] !== -1) {
                targets.add(`${target[0]} ${target[1]}`); // 좌표를 문자열로 저장 (중복 제거를 위해)
            }
        });

        // 적 제거
        targets.forEach(target => {
            const [x, y] = target.split(' ').map(Number);
            if (map[x][y] === 1) {
                count++;
                map[x][y] = 0;
            }
        });

        // 적 이동
        map.pop(); // 맨 아래 행 제거
        map.unshift(new Array(m).fill(0)); // 새로운 빈 행 추가

        time--; 
    }

    return count;
}

// 사정거리 내에서 가장 가까운 적 찾기
function possible(x, y, map) {
    let minDist = d + 1;
    let target = [-1, -1]; // 적이 없으면 [-1, -1] 반환

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (map[i][j] === 1) {
                const dist = Math.abs(x - i) + Math.abs(y - j);
                if (dist <= d) {
                    if (dist < minDist || (dist === minDist && j < target[1])) {
                        minDist = dist;
                        target = [i, j];
                    }
                }
            }
        }
    }

    return target;
}

// 궁수 배치의 모든 경우 탐색
dfs([], 0);

console.log(max);

 

내가 다시 풀 때 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [n,m,d] = input.shift().split(' ').map(v => +v); 
const graph = input.map(el => el.split(' ').map(v => +v)); 
//dfs 함수로 궁수의 위치 완탐 
//그때의 궁수로 제일 가까운 위치 구하기 
//가깝고 & 왼쪽 적 공격하기 
//-while n 만큼 
//-아래 삭제 위에 0 빈칸 추가 

let max = 0; 

function dfs(archers, idx){
    if(archers.length === 3){
        let map = graph.map(el => el.slice())
        max = Math.max(max, attack(archers, map))
        return; 
    }
    for(let i=idx; i<m; i++){
        archers.push(i)
        dfs(archers, i+1)
        archers.pop()
    }
}

dfs([], 0)
console.log(max)


//해당 궁수로 여러번 공격 
function attack(archers, map){
    let result = 0; 
    let cnt = n 
    
    while(cnt > 0){
        let set = new Set() //제거할 적 위치 
        archers.forEach(c => {
            let target = [-1,-1]; 
            let minDis = d
            for(let i=0; i<n; i++){
                for(let j=0; j<m; j++){
                    if(map[i][j] === 1){
                        let total = Math.abs(n-i) + Math.abs(c-j)
                        if((total === minDis && (j< target[1] || target[1] === -1)) 
                          || (total < minDis)){
                               target = [i,j]; 
                               minDis = total 
                        }
                    }
                }
            }
           if(target[0] !== -1 && target[1] !== -1){
                set.add(`${target[0]} ${target[1]}`)
           }
        })
       result += set.size
       let arr = [...set].map(el => el.split(' ').map(v => +v))
        for(let [x,y] of arr){
            if(x === -1 || y=== -1) continue; 
                map[x][y] = 0 
            }
        map.pop()
        map.unshift(new Array(m).fill(0))
        cnt-- 
    }
    return result; 
}