[백준 7576 / JavaScript] 토마토

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

✅ 문제 설명

❌ 1차 제출 (실패)

const fs = require("fs");
let input = fs.readFileSync("./19주차/김선구/input.txt").toString().split("\n");

const [col, row] = input.shift().split(" ").map(Number);
let graph = input.map((row) => row.split(" ").map(Number));
let visited = Array.from({ length: row }, () => Array(col).fill(0));

let q = [];

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (graph[i][j] === 1) {
      q.push([i, j]);
      visited[i][j] = 1;
    }
  }
}

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

while (q.length) {
  const [x, y] = q.shift();

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    if (
      nx >= 0 &&
      nx < row &&
      ny >= 0 &&
      ny < col &&
      graph[nx][ny] === 0 &&
      visited[nx][ny] === 0
    ) {
      visited[nx][ny] = visited[x][y] + 1;
      q.push([nx, ny]);
    }
  }
}

let cnt = 0;
let flag = true;

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (graph[i][j] === 0 && visited[i][j] === 0) {
      console.log(-1);
      flag = false;
      break;
    }
    if (visited[i][j] > cnt) {
      cnt = visited[i][j];
    }
  }
  if (!flag) break;
}

if (flag) {
  console.log(cnt - 1);
}

✅ 2차 제출 (성공)

const fs = require("fs");
let input = fs.readFileSync("./19주차/김선구/input.txt").toString().split("\n");
const [col, row] = input.shift().split(" ").map(Number);
let graph = input.map((row) => row.split(" ").map(Number));
let visited = Array.from({ length: row }, () => Array(col).fill(0));


let q = [];
// 인덱스 변수
let head = 0;

// 초기 작업. 반복문 돌면서 익은 토마토 q에 미리 넣기
for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (graph[i][j] === 1) {
      q.push([i, j]);
      visited[i][j] = 1;
    }
  }
}

// 방향
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

// 인덱스 값이 배열의 길이를 넘지 않으면
while (head < q.length) {
  const [x, y] = q[head++];
  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    if (
      nx >= 0 &&
      nx < row &&
      ny >= 0 &&
      ny < col &&
      graph[nx][ny] === 0 &&
      visited[nx][ny] === 0
    ) {
      visited[nx][ny] = visited[x][y] + 1;
      q.push([nx, ny]);
    }
  }
}

// 카운팅 작업
let cnt = 0;
// 안 익은 토마토 발견하기 위한 flag
let flag = true;

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (graph[i][j] === 0 && visited[i][j] === 0) {
      console.log(-1);
      flag = false;
      break;
    }
    // 더 지난 날짜 만나면 cnt 바꾸기
    if (visited[i][j] > cnt) {
      cnt = visited[i][j];
    }
  }
  if (!flag) break;
}

if (flag) {
  console.log(cnt - 1);
}

✅ 풀이 설명

1. queue에 익은 토마토를 먼저 배치
2. 익은 토마토가 들어있는 queue -> bfs 실행
3. visited 배열에 진행 날짜 +1 하면서 체크
4. bfs 종료되면 visited 배열 확인 -> 반복문으로 진행하면서 0 (안 익은 토마토)가 있는지 확인
5. 안 익은 토마토 있으면 -1 출력
6. 끝까지 돌았는데 안 익은 토마토 없으면 visited 배열의 최대값 출력

추가 설명

문제 상황

• 이번 문제를 풀고 실행시켰을 때 원하는 값이 잘 나왔다. 그리고 제출해보니 시간 초과라고 해서 gpt한테 물어보니,, shift() 때문에 시간 초과가 뜬 것. shift 메서드는 큐의 첫 번째 요소를 제거할 때마다 배열의 모든 요소를 이동시킨다. 그렇기 때문에 O(n) 시간 복잡도를 갖는다. 이 부분에서 시간복잡도를 줄여야 하는 상황이었다.
• 해결 방법
  인덱스를 넣을 변수를 사용하는 것이다.
  기존에 배열에 shift 메서드를 사용하게 되면 배열의 첫 번째 요소를 뽑아오는 방식인데, 인덱스를 사용하는 방식은 배열에 포인터를 지정해서 값을 뽑아온다. 뽑아오고 난 후에는 포인터++ 를하여 포인터를 한 칸 이동시켜서 다음 요소를 볼 수 있게 한다.