[JS] 백준 16236 : 아기상어

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

16236번: 아기 상어

 

 

풀이방법

1.상어좌표 뽑아낸 후 주어진 공간에 상어 좌표는 0으로 만들기!

2. 먹을 수 있는 물고기가 없을 때 까지 반복

 -3. BFS로 상어의 현 위치에서 먹을 수 있거나 지나갈 수 있는 물고기가 있는 공간의 좌표와 거리를 배열에 모음(fish_Arr)

 -4.먹을수 있거나 지나갈 수 있는 물고기 좌표 배열에서 먹을 수 있는 물고기가 있는 좌표와 거리만 추출(pos_Arr)

    ->이때 먹을 수 있는 물고기가 있는 좌표가 없으면 엄마상어 호출(종료)

 

 -6.먹을 수 있는 물고기가 있는 배열을 정렬함

   -1. 거리가 같으면 y좌표(행)순으로 오름차순

   -2.y좌표행)이 같으면 x좌표(열)순으로 오름차순

   -3. 둘다 아니면 거리순으로 오름차순

 

 -7. 정렬한 배열에서(pos_Arr) 제일 첫 번째 요소를 빼줌(pos.shift())

   -상어가 그 첫번째 요소의 좌표로 이동

   -주어진 공간에(arr) 상어가 물고기 먹었으니까 0으로 만들어줌

   -상어가 먹은 횟수 +1 (cnt)

 

 -8. 만약 cnt가 상어의 크기만큼 되었다면 상어의 크기 +1 증가

 -그리고 cnt는 0으로 만들어줌 (크기가 커졌으니까 초기화)

 

 -9.위를 반복

🤟내 제출

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=Number(input.shift());
let arr=[]
let dy=[0,1,-1,0]
let dx=[1,0,0,-1]
for(var i=0;i<N;i++){
    arr.push(input.shift().split(" ").map(Number))
}
let shark=[];
for(var i=0;i<arr.length;i++){
    for(var j=0;j<arr.length;j++){
        if(arr[i][j]==9) {
            arr[i][j]=0;
            shark=[i,j,2];
        }
    }
}
let answer=0
let cnt=0;
while(1){
    let pos=[];
    let fish=[];
    
    //상어좌표에서 먹을 수 있는 물고기와 지나갈 수 있는 물고기의 거리와 그 좌표를 저장 : fish
    let visited=Array.from({length:N},()=>Array(N).fill(false));
    visited[shark[0]][shark[1]]=true;
    let queue=[];
    queue.push([shark[0],shark[1],0]);
    while(queue.length){
        let [y,x,len]=queue.shift();
        for(var i=0;i<4;i++){
            let ny=y+dy[i];
            let nx=x+dx[i];         
            if(nx>=0 && ny>=0 && nx<N && ny<N && shark[2]>=arr[ny][nx]){
                if(!visited[ny][nx]){
                    visited[ny][nx] = true;            
                    if(arr[ny][nx]!=0){
                        fish.push([ny,nx,arr[ny][nx],len+1])
                    }
                    queue.push([ny,nx,len+1])
                } 
            }
        }

    }
    //먹을 수 있는 물고기를 찾음 : pos
    fish.forEach((fi)=>{
        if(shark[2]>fi[2]){
            pos.push([fi[0],fi[1],fi[3]]);
        }
    })

    if(pos.length==0) break;
    //먹을수 있는 물고기의 순서
    pos.sort((a,b)=>{
        if(a[2]==b[2]){
            if(a[0]==b[0]) return a[1]-b[1];
            else return a[0]-b[0];
        }
        else return a[2]-b[2]
    })
    //상어가 가장 가까운 물고기를 먹고 그 쪽으로 이동
    answer+=pos[0][2];
    shark[0]=pos[0][0];
    shark[1]=pos[0][1];
    arr[pos[0][0]][pos[0][1]]=0;
    pos.shift();
    cnt++;
    //상어 크기 증가
    if(shark[2]==cnt){
        shark[2]++;
        cnt=0;
        
    }
    
    
}
console.log(answer)

 

 

💢어려웠던 이유

1.상어가 만약 가장 가까운 물고기를 먹고 이동하거나 크기가 커졌다면

 ->다시 모든 물고기와의 거리와 좌표를 새로 저장하고 정렬해야했다.

 ->즉 상어에게서 가능한 물고기의 좌표와 거리를 찾고

 ->먹을 수 있는 물고기를 찾고

 ->정렬하고

 ->정렬한 배열에서 가장 첫번째 있는 물고기를 먹고 상어가 이동하고 (진화할수도있고 안할 수도있음)

 -> 다시 위 과정을 반복해야한다.(물고기 한번먹으면 다시 BFS)

 

2. y좌표와 x좌표에서 계속 순서를 바꿔 오타가 났었다.

 -항상 조심하자...