백준 7576번

QUESTION LINK

익은 토마토가 위치한 곳에서 한 번씩 BFS를 시행해, 하루가 지날 때마다 근처 토마토가 익은 것으로 만드는 형식을 적용하고자 했습니다. 즉, 이를 위해서 익은 토마토가 있는 위치 ‘1’ 좌표를 찾아내고, 이 곳에서 BFS가 순차적으로 발생하는 것으로 하고자 구상했습니다. 생각한 순서는 아래와 같습니다.

1. 모든 익은 토마토(’1’)의 좌표 구하기
2. 하루가 지날 때마다(day+=1;) 익은 토마토의 좌표로부터 근접한 덜 익은 토마토(’0’)의 값을 ‘1’로 바꾸기
3. 다음 하루가 지날 때마다 2번과 같은 과정 반복하기
4. 인접한 곳에 덜 익은 토마토(’0’)가 없을 시 과정 중단하기

성공은 했으나 시간 초과

이를 위해, 아래와 같은 코드를 구상했으며, 이를 통해 순차적으로 토마토가 익는 과정을 그려낼 수 있었습니다. 하지만, 시간 초과가 발생해, 추가적인 수정이 필요했습니다.

const [numbers, ...graph] = input;
const [m, n] = numbers.split(" ").map((value) => Number(value));
const graphBoxes = graph.map((line) => line.split(" "));
const queue = [];
// 첫 익은 토마토가 있는 위치를 받음

const getMarker = (y, x) => `${y},${x}`;
const getQueueItem = (y, x, day) => `${getMarker(y, x)},${day}`;
// queue에 들어갈 형태를 만드는 함수

graphBoxes.forEach((line, lineIndex) => {
  line.forEach((box, boxIndex) => {
    if (box === "1") queue.push(getQueueItem(lineIndex, boxIndex, 0));
    // 익은 토마토가 있을 경우, queue 배열에 담아줌
  });
});

const visited = {};
// 방문 여부를 나타내는 객체
let day = 0;
// 날짜를 나타냄. 하루가 지나는 것을 확인할 때마다 1씩 오름
let curItem;
// 반복문에서 현재의 위치를 나타내는 값

while (queue.length) {
  curItem = queue.shift();
  // queue에서 가장 처음 요소를 가져와, BFS로 순환하도록 함
  const [y, x, curDay] = curItem.split(",").map((value) => Number(value));
  // 좌표 및 날짜를 가져옴
  const curValue = graphBoxes[y][x];
  const curMarker = getMarker(y, x);

  if (!visited[curMarker] && curValue !== "-1") {
    // 방문하지 않았고, 토마토가 있는 경우에만 추가 작업 시행함
    visited[curMarker] = true;
    // 방문했음을 표기
    graphBoxes[y][x] = "1";
    // 토마토가 있었다는 표기
    if (day < curDay) day = curDay;
    // 현재 설정된 날짜보다 많은 날짜가 지나갔을 시, 그 날짜로 수정
    if (y - 1 >= 0) queue.push(getQueueItem(y - 1, x, curDay + 1));
    if (x - 1 >= 0) queue.push(getQueueItem(y, x - 1, curDay + 1));
    if (y + 1 < n) queue.push(getQueueItem(y + 1, x, curDay + 1));
    if (x + 1 < m) queue.push(getQueueItem(y, x + 1, curDay + 1));
    // 주변 토마토들을 체크하기 위해 날짜가 하루 더해진 값(curDay + 1)을 대입함
  }
}

const isFailed = !!graphBoxes.find((line) => line.find((box) => box === "0"));
// 모든 토마토가 순환한 후, 방문하지 못한 곳이 존재할 시 -1로 변경
const result = isFailed ? -1 : day;

console.log(result);

시간 초과 원인 제거하기

이 코드에서 시간 초과가 나오게 된 원인 중 하나로, queue.shift() 부분이 있으며, 이 부분은 index로 받아 처리하는 방법으로 해결이 가능했습니다. 그리고 다른 원인 중 하나는 위 코드에서 일단 방문한 적이 있는 지를 확인하고 추가적인 작업을 하는게 아니라, 우선 queue에 담은 뒤, 추가 작업에서 방문 여부를 확인하고 진행하도록 설정이 되어있었습니다. 이로 인해 불필요한 작업이 반복되는 경우가 많아져, 이 부분들을 모두 제외하고 코드를 수정했습니다.

const input = fs.readFileSync(filePath).toString().trim().split("\n");
const [numbers, ...graph] = input;
const [m, n] = numbers.split(" ").map((value) => +value);
const graphBoxes = graph.map((line) => line.split(" "));
const queue = [];
const visited = {};
// 주변 좌표로 넘어가는 부분의 중복을 없애기 위해 만든 위치 변수들
const positionValue = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

const getMarker = (y, x) => `${y},${x}`;
const getQueueItem = (y, x, day) => `${getMarker(y, x)},${day}`;
// 이전과 달라진 부분. 좌표와 날짜를 받고, 이상이 없을 시 queue에 들어가도록 설정함
const checkPosition = (y, x, day) => {
  if (x < 0 || x >= m || y < 0 || y >= n) return;
  const marker = getMarker(y, x);
  if (visited[marker]) return;
  visited[marker] = true;
  queue.push(getQueueItem(y, x, day + 1));
};

// 이전과 달리, queue에 들어가기 전 방문 여부를 체크해 중복 확인이 발생하지 않도록 함
graphBoxes.forEach((line, lineIndex) => {
  line.forEach((box, boxIndex) => {
    if (box === "1") {
      visited[getMarker(lineIndex, boxIndex)] = true;
      queue.push(getQueueItem(lineIndex, boxIndex, 0));
    }
  });
});

let targetIdx = 0;
let day = 0;
let curItem;

// 기존에 queue에서 직접 빼던 방식과 달리, queue내에서 index를 통해 빼낸 것과 동일한 효과로 필요한 값들을 꺼냄
while (queue[targetIdx]) {
  curItem = queue[targetIdx];
  targetIdx += 1;

  const [y, x, curDay] = curItem.split(",").map((value) => +value);
  const curValue = graphBoxes[y][x];

  if (curValue !== "-1") {
    graphBoxes[y][x] = "1";
    if (day < curDay) day = curDay;
    // 주변 위치로 이동하도록 설정하는 부분
    positionValue.forEach(([dy, dx]) => checkPosition(y + dy, x + dx, curDay));
  }
}

const isFailed = !!graphBoxes.some((line) => line.some((box) => box === "0"));
const result = isFailed ? -1 : day;

console.log(result);

🔎 위와 같이 수정을 하여, 백준에서 통과를 하기는 했습니다. 하지만, 이 코드의 경우에도 시간이 상당히 오래 걸려 통과가 됐기 때문에 가능하다면 자바스크립트에서 더 빠르게 처리하는 코드를 찾아보아야 합니다.

GITHUB  EMAIL