[백준/JS] 토마토 7576

문제

📝 문제풀이

완전탐색을 진행해야 하는 문제입니다.
최소 일 수라서 bfs를 사용해주었습니다!

제가 실수했던 것들

1. 날짜 세는 전역 변수를 따로 만듦

let day=0;
function bfs(sx,sy) {
	
  	let queue = [[sx,sy,0]];
  	let [x,y,cnt] = [0,0,0];

    while (queue.length) {
        [x, y,cnt] = queue.shift();

        for (let d = 0; d < 4; d++) {
            let nx = x + dx[d];
            let ny = y + dy[d];

            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (box[ny][nx] === 0) {
                    box[ny][nx] = 1;
                    queue.push([nx, ny,cnt+1]);
                }
            }
        }
    }
  
  day+=cnt;
}

위와 같이 짰습니다.
이렇게 했더니 예제 3번에 어긋났습니다.

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

결과// 6

이렇게 하면

[
  [ 1, -1, 7, 6, 5, 4 ],
  [ 2, -1, 6, 5, 4, 3 ],
  [ 3, 4, 5, 6, -1, 2 ],
  [ 4, 5, 6, 7, -1, 1 ]
]

잘 나왔을때 결과가 저것인데 보면 처음 1의 위치에서 동시에 토마토가 익어나가는 것을 확인할 수 있습니다.

허나 제가 원래대로 짠 코드면 동시에 익는다고 보지않고 두 시작점을 따로따로보기 때문에 시작점인 [0,0] 과 [5,3] 이 사실 동시에 일어나는 건데 각각 다른날로 보게 되기때문에 결과가 9로 잘못나오게 됩니다.

2. 시간초과

shift() 함수를 사용하면 시간초과가 난다는 글을 찾았습니다.
그래서 idx를 사용하는 방식으로 변경했습니다.

참고

📝 결과코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './test.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

let [M, N] = input.shift().split(' ').map(Number);

let box = [];
let queue = [];
let dx = [0, 0, -1, 1];
let dy = [-1, 1, 0, 0];

for (let y = 0; y < N; y++) {
    box.push(input.shift().split(' ').map(Number));
    for (let x = 0; x < M; x++) {
        if (box[y][x] === 1) {
            queue.push([x, y]);
        }
    }
}

function bfs() {
    let idx = 0;

    while (queue.length != idx) {
        [x, y] = queue[idx];

        for (let d = 0; d < 4; d++) {
            let nx = x + dx[d];
            let ny = y + dy[d];

            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (box[ny][nx] === 0) {
                    box[ny][nx] = box[y][x] + 1;
                    queue.push([nx, ny]);
                }
            }
        }
        idx++;
    }
}

bfs();
console.log(box);

res = box[0][0] - 1;

for (let x = 0; x < M; x++) {
    for (let y = 0; y < N; y++) {
        if (box[y][x] === 0) {
            return console.log(-1);
        }
        if (res < box[y][x]) res = box[y][x] - 1;
    }
}

console.log(res);

홈난했떤...흔적