[JS] 백준 17135 : 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

📋풀이방법

1. 3명의 궁수를 배치할 모든 경우의 수를 반복한다.

2. 한명의 궁수가 처치할 적의 좌표를 구한다.

 -BFS로 진행한다.

 -먼저 궁수는 N+1행에 있으므로 BFS의 시작은 [ N , 궁수가 배치한 열] 부터 시작한다.

 -visited 필수

 -BFS로 왼쪽 -> 위 -> 오른쪽 순으로 검사하면서 거리가 K이하인 곳은 큐에 넣어준다.

 -거리가 K이하인 곳을 넣다가 만약 1인 곳을 발견하면 해당 좌표를 return해서 BFS를 종료한다. - 가장가까운 적이므로

3.위와 같은 한명의 궁수가 적을 찾는 BFS를 모든 궁수가 수행한다.

4. 3명의 궁수는 현재 자신이 처치할 적의 좌표를 얻었다.

5. 해당 좌표를 0으로 만들면서 만약 해당 좌표가 이미 0이 되었다면 적처치를 증가시키지않는다 -> 같은 적 동시에 사격가능

6. 적의 이동은 arr배열을 pop해서 마지막 열을 통째로 날리고, 새로운열 을 unshift해서 모든 열을 한칸 씩 내려준다.

7. 모든 열을 내리고 해당 과정에서 처치한 적의 수를 현재 최대값인지 검사하고 저장한다.

 

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,M,K]=input.shift().split(" ").map(Number);
let arr=[];
let refresh=[];
for(var i=0;i<N;i++){
    arr.push(input.shift().split(" ").map(Number));
    refresh.push(arr[i].slice());
}

let t=Array(M).fill(0);

//위,왼쪽, 오른쪽
let dx=[-1,0,1];
let dy=[0,-1,0]

let visited=[];

//한명의 궁수가 처치할 적의 좌표
function start(y,x){
    let queue=[];
    queue.push([y,x]);
    while(queue.length){
        let [ty,tx]=queue.shift();
        for(var i=0;i<3;i++){
            let nx=tx+dx[i];
            let ny=ty+dy[i];
            let poss=Math.abs(x-nx)+Math.abs(y-ny);
            if(nx>=0 && ny>=0 && nx<M && ny<N && poss<=K && visited[ny][nx]==0){
                visited[ny][nx]=1;
                if(arr[ny][nx]==1){
                    return [ny,nx];
                }
                queue.push([ny,nx]);
            }
        }
        
    }
}

let result=0;
//3명의 궁수가 배치되는 모든 경우의수를 반복해야함
for(var i=0;i<M;i++){
    for(var j=i+1;j<M;j++){
        for(var k=i+2;k<M;k++){
            let answer=0;
            //적이 다 아래로 이동할때 까지
            for(var z=0;z<N;z++){
            	//각각 한명의 궁수가 처치할 적의 좌표를 BFS를 호출해 구함
                //visited로 무한반복이 안되게해줌
                visited=Array.from({length:N},()=>Array(M).fill(0));
                let check1=start(N,i);

                visited=Array.from({length:N},()=>Array(M).fill(0));
                let check2=start(N,j);

                visited=Array.from({length:N},()=>Array(M).fill(0));
                let check3=start(N,k);
				
                //각각 궁수가 처치할 좌표가 있다면
                //해당 좌표를 0으로 만들고 처치수 증가시킴
                if(check1){
                    let [ty,tx]=check1;
                    if(arr[ty][tx]!=0){
                        answer++
                    }
                    arr[ty][tx]=0;
                }
                if(check2){
                    let [ty,tx]=check2;
                    //만약 이미 0이 되어있다면 동시에 처치한 것이므로 증가취소
                    if(arr[ty][tx]!=0){
                        answer++
                    }
                    arr[ty][tx]=0;
                    
                }
                if(check3){
                    let [ty,tx]=check3;
                    if(arr[ty][tx]!=0){
                        answer++
                    }
                    arr[ty][tx]=0;
                }
                //적 이동
                arr.pop();
                arr.unshift(t);
    
            }
            result=Math.max(result,answer);
            //적이 배치된 배열을 다시 새로고침해줌
            arr=refresh.map(v=>[...v])
        }
    }
}
console.log(result);

 

💢어려웠던점

1.처음에 DFS로 진행해버려서 적을 처치하는 우선순위 조건을 실패했다.

 -BFS로 왼쪽 -> 위 -> 오른쪽 순으로 검사를 진행해야 우선순위 조건을 충족한다.

-이런식으로 진행하면 정면 -> 왼쪽 -> 정면+1 -> 오른쪽... 을 검사하게되면서 우선순위 조건을 충족한다.

2. 항상 배열은 깊은복사를 진행하자.

 -slice로 1차원 배열 복사

 -map으로 2차원 배열 복사