[JS] 백준 7576 : 토마토 - 구현문제(골드)

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

7576번: 토마토

 

📋풀이방법

1. 익은토마토의 좌표를 뽑아내서 well에 저장한다.

2. 익은 토마토의 상하좌우에 익지않은 토마토가 있으면 그 좌표를 저장하고 익었음을 표시한다.

 -이때 현재 날짜를 같이 넣어준다.

3. 다음 익은 토마토의 좌표의 상하좌우를 검사한다. 이때 현재날짜를 계속해서 cnt에 초기화시킨다,

 -마지막에 토마토를 모두 검사한 날짜를 위해

4. shift가 아닌 idx라는 변수를 이용해서 진행한다 -> 시간초과 문제임

 

🤟내 제출

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]=input.shift().split(" ").map(Number);
let arr=[];
for(var i=0;i<M;i++){
    arr.push(input.shift().split(" ").map(Number));
}
let well=[];
let no_well=0;
for(var i=0;i<M;i++){
    for(var j=0;j<N;j++){
        if(arr[i][j]==1){
            well.push([i,j,0]);
        }
        else if(arr[i][j]==0){
            no_well++;
        }
    }
}

let dx=[1,0,0,-1];
let dy=[0,1,-1,0];
let cnt=0;

let idx=0;
while(well.length!=idx){
    let [y,x,pos]=well[idx]
    for(var i=0;i<4;i++){
        let nx=x+dx[i];
        let ny=y+dy[i];
        if(ny>=0 && nx>=0 && ny<M && nx<N ){
            if(arr[ny][nx]==0){
                
                arr[ny][nx]=1;
                no_well--;
                well.push([ny,nx,pos+1]);
            }
        }
    }
    idx++;
    cnt=pos
}
console.log(no_well>0 ? -1 : cnt);

💢어려웠던 점

1. 시간초과가 계속 떳는데 문제가 뭔지 몰랐다.

 -검색해서 shift() 가 문제였던것을 알았고, 이를 idx라는 변수를 증가시키면서 well 배열을 순회했다.

2. 토마토가 익을 때의 날짜를 계산하지 못했다.

 -토마토를 검사할 때마다 날짜를 계산하면 하나하나씩 상하좌우를 검사할 때마다 카운팅되기때문에 답이아니다.

 -익은토마토의 좌표를 저장할때 익기전의 날짜에서 +1을 한 값을 같이 저장해줌으로써 마지막에 토마토를 상하좌우 검사한 날짜를 알 수 있다.