[Algorithm] 백준 7569번-토마토

백준 7569번-토마토

문제 파악

• 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수 구하기
  • 1 : 익은 토마토
  • 0 : 익지 않은 토마토
  • -1 : 토마토가 들어있지 않은 칸
• 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미

📌 백준 7569번 문제 링크

문제만 보았을 때 떠오르는 풀이방법은,,,

1. 기존의 BFS와 동일하게 가되, “위, 아래”의 방향도 접근하기
   • x,y만 사용했다면 x,y,z로 3차원 배열 사용
2. 토마토가 익고, 방문한적 없는 경우 BFS 돌기

1. 처음 짠 코드 왜틀렸지 ?

let [size, ...input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [M, N, H] = size.split(" ").map(Number);
input = input.map((i) => i.split(" ").map(Number));
const tomatos = [];
const dist = [];
let day = 0;

for (let i = 0; i < input.length; i += N) {
  tomatos.push(input.slice(i, i + N));
  dist.push(
    Array.from({ length: N }, () => Array.from({ length: M }, () => -1)),
  );
}

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

const bfs = (startX, startY, startZ) => {
  const queue = [[startX, startY, startZ]];
  dist[startX][startY][startZ] = 1;

  while (queue.length > 0) {
    const [x, y, z] = queue.shift();

    for (let dir = 0; dir < 6; dir++) {
      const [nx, ny, nz] = [x + dx[dir], y + dy[dir], z + dz[dir]];
      if (nx < 0 || nx >= H || ny < 0 || ny >= N || nz < 0 || nz >= M) continue;
      if (dist[nx][ny][nz] !== -1 || tomatos[nx][ny][nz] !== 0) continue;

      queue.push([nx, ny, nz]);
      dist[nx][ny][nz] = dist[x][y][z] + 1;
    }
  }
};

for (let x = 0; x < H; x++) {
  for (let y = 0; y < N; y++) {
    for (let z = 0; z < M; z++) {
      if (tomatos[x][y][z] == -1) dist[x][y][z]++;
      if (tomatos[x][y][z] == 1 && dist[x][y][z] == -1) {
        bfs(x, y, z);
      }
    }
  }
}

for (let x = 0; x < H; x++) {
  for (let y = 0; y < N; y++) {
    for (let z = 0; z < M; z++) {
      if (dist[x][y][z] < 0) return console.log(-1);
      else day = Math.max(day, dist[x][y][z] - 1);
    }
  }
}

console.log(day);

오류 지점

1. BFS 시작 설정 방식의 문제

• 틀린 코드에서는 bfs(x, y, z)를 익혀있는 토마토마다 매번 호출됨
• 여러 개의 BFS가 따로따로 돌아가게 만드는 구조
  • 즉, 여러 BFS에서 동일한 토마토를 서로 다른 시간으로 방문할 수 있음
  • dist[x][y][z]를 1로 시작해서 +1씩 늘리지만, 다른 BFS가 들어와 덮어쓰는 문제도 생길 수 있음

이게 “다중 시작점 BFS”의 정석적인 방식 ! 하지만, 이 문제는 여러 시작점에서 동시에 퍼지는 전형적인 BFS 문제임

🔑 올바른 접근법

1. 초기 상태에서 익은 토마토 좌표를 전부 큐에 넣는다
   • 동시에 퍼지기 때문에 다중 시작점 BFS 필요
2. BFS를 한 번만 수행한다
   • 큐에서 하나씩 꺼내며 인접 노드로 확산
   • 방문 처리 (dist 갱신 및 queue.push())
3. 모든 노드를 다 돈 뒤
   • dist가 -1인 게 남아 있다면 → 익을 수 없는 토마토 → -1 출력
   • 없으면 dist의 최대값이 정답

💡 BFS는 “동시에 퍼져야” 하므로, 큐에 모든 시작점을 넣고 한 번에 돌리는 방식으로 구현!

수정한 코드

let [size, ...input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [M, N, H] = size.split(" ").map(Number);
input = input.map((i) => i.split(" ").map(Number));

const tomatos = [];
const dist = [];
const queue = [];

for (let i = 0; i < input.length; i += N) {
  tomatos.push(input.slice(i, i + N));
  dist.push(
    Array.from({ length: N }, () => Array.from({ length: M }, () => -1)),
  );
}

for (let x = 0; x < H; x++) {
  for (let y = 0; y < N; y++) {
    for (let z = 0; z < M; z++) {
      if (tomatos[x][y][z] == 1) {
        queue.push([x, y, z]);
        dist[x][y][z] = 0;
      } else if (tomatos[x][y][z] == -1) dist[x][y][z] = 0;
    }
  }
}

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

let qIdx = 0;

while (qIdx < queue.length) {
  const [x, y, z] = queue[qIdx++];

  for (let dir = 0; dir < 6; dir++) {
    const [nx, ny, nz] = [x + dx[dir], y + dy[dir], z + dz[dir]];

    if (nx < 0 || nx >= H || ny < 0 || ny >= N || nz < 0 || nz >= M) continue;
    if (dist[nx][ny][nz] !== -1 || tomatos[nx][ny][nz] !== 0) continue;

    dist[nx][ny][nz] = dist[x][y][z] + 1;
    queue.push([nx, ny, nz]);
  }
}

let day = 0;

for (let x = 0; x < H; x++) {
  for (let y = 0; y < N; y++) {
    for (let z = 0; z < M; z++) {
      if (dist[x][y][z] < 0) return console.log(-1);
      day = Math.max(day, dist[x][y][z]);
    }
  }
}

console.log(day);

---

이번 문제는 푸는데 시간이 걸렸고, 결국 gpt를 사용해서 문제점을 발견할 수 있었다.
아예 의문을 갖지못하니깐 문제점도 전혀 눈에 안보였다,, 비슷한 문제도 풀어봤으면서 어째서 !!
아무튼 이 문제에서 기억해야할 것은 “BFS는 “동시에 퍼져야” 하므로, 큐에 모든 시작점을 넣고 한 번에 돌리는 방식 사용” 이다. 절대 잊지 말자 !

---

END