[JS] 백준 7569번 : 토마토(3차원배열) - 구현문제

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

7569번: 토마토

이전에 토마토문제에서 3차원배열을 추가한 것이다.

 

 

📋풀이방법

1. 처음에 익은토마토의 위치를 저장한다(well배열) -> 이때 좌표에 0을 추가해서 저장한다(며칠이 걸렸는지를 위해)

 -처음에 안익은 토마토의 갯수를 세놓는다.(none_well)

 -visited도 3차원 배열로 선언해줘야한다.

2. [시간초과 주의] well배열의 idx가 well의 length만큼 되었을 때 반복을 멈춘다.

 -1. 익은 토마토의 위치 well배열에서 idx로 꺼내면서 방문한다(visited), -> [z,i,j,pos]

 -2. 익은 토마토의 좌표에서 상하좌우를 검사하고 위, 아래를 위해 2번의 검사를 추가한다. 

   -1. 검사하면서 방문표시를 1로 해주고, 안익은 토마토는 1로 바꿔준다.

   -2. 그리고 안익은 토마토의 갯수를 -1 해준다.

   -3. 그리고 well배열에 해당 좌표와 pos+1한 값을넣어준다 -> 날짜가 +1일 지났다는 의미

 3. 상하좌우 위, 아래 검사가 끝나면 안익은 토마토의 갯수가 0인지 검사한다 -> 0이면 반복을 멈춤

 4. 0이 아니라면 idx를 +1해주고, 날짜 카운트는 현재 pos값으로 저장한다

 

🤟내 제출

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 [M,N,H]=input.shift().split(" ").map(Number);
let arr=[];
for(var i=0; i<H;i++){
    let temp=[];
    for (let j = 0; j < N; j++) {
        temp.push(input.shift().split(' ').map(Number));
    }
    arr.push(temp.map(v=>[...v]));
}
//익은토마토 좌표 미리 추출
let well=[];
let none_well=0;
for(var z=0;z<H;z++){
    for(var i=0; i<N;i++){
        for (let j = 0; j < M; j++) {
            if(arr[z][i][j]==1){
                well.push([z,i,j,0])
            }
            else if(arr[z][i][j]==0){
                none_well++;
            }
        }
    }
}

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



let visited_temp=Array.from({length:N},()=>Array(M).fill(0));
let visited=[];
for(var i=0; i<H; i++){
    visited.push(visited_temp.map(v=>[...v]))
}


function DFS(hei,y,x,pos){
    for(var i=0;i<4;i++){
        let nx=x+dx[i];
        let ny=y+dy[i];
        if(nx>=0 && ny>=0 && ny<N && nx<M && visited[hei][ny][nx]==0){
            if(arr[hei][ny][nx]==0){
                visited[hei][ny][nx]=1;
                arr[hei][ny][nx]=1;
                none_well--;
                well.push([hei,ny,nx,pos])
            }
        }
    }
    for(var i=0;i<2;i++){
        let nz=hei+dz[i];
        if(nz>=0 && nz<H && visited[nz][y][x]==0){
            if(arr[nz][y][x]==0){
                visited[nz][y][x]=1;
                arr[nz][y][x]=1;
                none_well--;
                well.push([nz,y,x,pos])
                
            }
        }
    }
}
let cnt=0;
let idx=0;
while(well.length!=idx){
    //토마토 전이
    let [z,i,j,pos]=well[idx];
    visited[z][i][j]=1;
    DFS(z,i,j,pos+1);


    if(well.length==0){
        break;
    }
    idx++;
    cnt=pos;
}

console.log(none_well>0 ? -1 : cnt)

💢어려웠던 점

1. visited 3차원 선언

let visited_temp=Array.from({length:N},()=>Array(M).fill(0));
let visited=[];
for(var i=0; i<H; i++){
    visited.push(visited_temp.map(v=>[...v]))
}

2. 시간초과

- 이전 토마토 문제에서도 똑같이 시간초과때문에 헤맸다.

-shift가 아닌 idx로 익은토마토의 좌표를 꺼내야한다.

3. 날짜 계산

-이전 토마토 문제에서도 똑같이 날짜계산에서 헤맸다.

-처음에 익은 토마토 좌표에 현재 날짜 값을 넣어서 새롭게 익은 토마토를 추가할 때 현재 날짜값에 +1한 값을 넣어준다.

-이를 반복을 하면서 계속 날짜 카운트에 저장한다.