[백준5427_자바스크립트(javascript)] - 불

🔴 문제

불

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [tc, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

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

let front = 0;

// 1. 각각의 테스트 케이스 분리
while (front < inputs.length) {
  const [w, h] = inputs[front++].split(' ').map(Number);
  const maps = [];
  const fire = [];
  const q = [];
  const fireQ = [];
  let fireFront = 0;
  let qFront = 0;

  // 2. 맵 만들기
  for (let i = 0; i < h; i++) {
    const map = inputs[front++].split('');
    maps.push([...map]);
    fire.push([...map]);
  }

  // 3. 시작 좌표 찾기
  // 불이거나, 상근이면 큐에 삽입
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (maps[i][j] === '*') {
        fireQ.push([i, j]);
        fire[i][j] = 1;
      }
      if (maps[i][j] === '@') {
        q.push([i, j]);
        maps[i][j] = 1;
        fire[i][j] = '.';
      }
    }
  }

  // 4. 불이 각 위치에 도달할 수 있는 최단거리
  while (fireFront < fireQ.length) {
    const [x, y] = fireQ[fireFront++];

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

      if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
        if (fire[nx][ny] === '.') {
          fireQ.push([nx, ny]);
          fire[nx][ny] = fire[x][y] + 1;
        }
      }
    }
  }

  // 5. 상근이 이동
  while (qFront < q.length) {
    const [x, y] = q[qFront++];

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

      if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
        if (maps[nx][ny] === '.') {
          if (fire[nx][ny] === '.' || fire[nx][ny] > maps[x][y] + 1) {
            q.push([nx, ny]);
            maps[nx][ny] = maps[x][y] + 1;
          }
        }
      }
    }
  }

  let isEscape = false;
  let escapeCnt;
  // 6. 탈출 성공했는지 확인
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (i >= 1 && i < h - 1 && j >= 1 && j < w - 1) continue;
      if (typeof maps[i][j] === 'number') {
        if (isEscape) {
          escapeCnt = Math.min(maps[i][j], escapeCnt);
        } else {
          isEscape = true;
          escapeCnt = maps[i][j];
        }
      }
    }
  }

  if (isEscape) {
    console.log(escapeCnt);
  } else {
    console.log('IMPOSSIBLE');
  }
}

🟢 풀이

⏰ 소요한 시간 : -

눈물나는 채점 현황이다...
이 문제는 얼마전 풀이했던 불!문제에서 테스트케이스만 추가한 버전이라 복습차원으로 풀었는데 시간초과/틀렸습니다 콤보로 엄청 삽질했다...

시간초과의 명확한 이유는 모르겠으나 시간초과가 발생했을 법한 요소를 다 지워준 정답 코드를 분석해보겠다...!

1. 이 문제는 여러개의 테스트 케이스를 한번에 처리해야 한다. 따라서 1번의 위치에서 각각의 테스트 케이스를 분리해준다. 이때 inputs 배열에서 shift() 메서드로 w와 h값을 가져올 시 시간초과에 영향을 줄 수 있을 것 같아 인덱스로 변경해 주었다.

2. 하나의 테스트 케이스에 대한 maps(실제 맵), fire(불의 최소시간을 구할 맵)을 만들어준다. 여기서도 shift()메서드 사용 대신 인덱스를 사용한다.

3. 시작 좌표를 찾아준다. 만약 불(*)이라면, bfs를 수행해 줄 fireQ에 해당 좌표를 넣어주고 bfs 수행시 시간 측정을 하기 위해 불이 있던 초기 위치를 1로 초기화 시켜준다. 마찬가지로 상근이(@)라면 bfs를 수행해 줄 q 위치에 해당 좌표를 넣어주고 상근이가 있던 초기 위치를 1로 초기화 시켜준다. 이때 해당 위치에 fire배열의 값도 '.' 빈 곳으로 바꾸어준다. 바꿔주지 않아도되지만 불은 상근이가 있던 위치도 지나갈 수 있기 때문에 bfs에서 매번 해당위치가 빈칸인지, 상근이인지 아닌지 확인해줘야 한다.

4. 불이 각 위치에 도달할 수 있는 최단거리를 구하기 위해 bfs를 수행해준다. 여기서도 shift()메서드 사용 대신 인덱스를 사용한다. 상하좌우를 돌면서 범위가 올바르고, fire 배열의 위치가 '.'라면 지나갈 수 있도록 해준다. 처음에는 불이 벽이 아니면 다 지나갈 수 있으므로 fire[nx][ny] !== '#' 로 분기 처리를 했었는데 이 경우 불이 중복해서 들어가기 때문에 시간초과가 발생할 것 같아 조건을 수정해주었다.

5. 상근이가 각 위치에 도달할 수 있는 최단거리를 구하기 위해 bfs를 수행해준다. 여기서도 shift()메서드 사용 대신 인덱스를 사용한다. 상하좌우를 돌면서 범위가 올바르고, maps 배열의 위치가 '.'라면 지나갈 수 있는 길임은 확실하나, 불보다 먼저 도착했을 경우만 도착 가능하기에 두가지 조건을 확인해 준다.

   • 해당 위치가 불이 번지지 않은 곳인가?
   • 해당 위치가 불이 번졌지만 상근이보다 늦게 도착했는가 ?

   이 두가지 조건을 만족한다면 상근이가 건너갈 수 있는 지역이므로 q에 삽입 후 최단거리를 업데이트 해준다.

6. 마지막으로 for 문을 돌면서 가장 자리에 숫자가 있을 경우 탈출한 것이므로 탈출 처리를 하고 그 수중에서 최소값을 찾아주면 된다. 나는 원래 배열에 정답이 될 수 있는 값을 추가해놓고 마지막에 ...arr로 배열을 순회하며 최소값을 찾아주는 데 이 로직도 제거했다.

시간초과는 위에서 언급한 shift() 메서드 제거, 중복되는 bfs 수행 조건 제거, 불필요한 이터레이션 제거로 해결할 수 있었으나 계.속. 틀렸다. 계.속.
결국 질문게시판에 글을 썼고, 천사같은 분이 댓글을 남겨주셔서 해결할 수 있었다.

이 문제에서 w,h의 범위가 1000 미만이라 1001 로 탈줄 조건을 줬었는데 이게 원인이었다.(왜그랬니?) 수정했더니 정답...
그래도 bfs 로직에 문제가 없었음에 감사하다...

🔵 Ref

[백준4179_자바스크립트(javascript)] - 불!
https://www.acmicpc.net/board/view/146864