백준 / 그래프 / 2206번 / 벽 부수고 이동하기 / JS

문제 간단설명

 

• N×M 크기의 맵이 주어집니다
• 맵의 각 칸은 0(이동 가능) 또는 1(벽)입니다
• (1,1)에서 (N,M)까지 이동하려고 합니다
• 벽을 한 번만 부술 수 있는 능력이 있습니다
• 목표는 최단 경로의 길이를 찾는 것입니다

 

제한 사항

• 1 <= N <= 1,000
• 1 <= M <= 1,000
• (1, 1)과 (N, M)은 항상 0이다.

실패 코드 (시간 초과)

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

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

const EMPTY = 0;
const WALL = 1;

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

let result = Infinity;

function solution() {
  bfs();

  console.log(result === Infinity ? -1 : result);
}

function bfs() {
  const queue = [[0, 0, 1, false]];
  const visited = Array.from({ length: N }, () => Array(M).fill(false));

  visited[0][0] = true;

  while (queue.length > 0) {
    const [curRow, curCol, curCount, broken] = queue.shift();

    if (curRow === N - 1 && curCol === M - 1) {
      result = curCount;
      return;
    }

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      if (!isValid(nr, nc)) {
        continue;
      }
      if (visited[nr][nc]) {
        continue;
      }
      if (broken && map[nr][nc] === WALL) {
        continue;
      }

      visited[nr][nc] = true;

      if (map[nr][nc] === WALL && !broken) {
        queue.push([nr, nc, curCount + 1, true]);
      } else {
        queue.push([nr, nc, curCount + 1, broken]);
      }
    }
  }
}

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < M;
}

solution();

 

BFS를 이용해 문제를 풀었다. 2% 정도에서 시간초과가 났었는데, 문제는 BFS의 while문에 있었다.

while문에서 queue의 맨 앞의 요소를 뽑아내기 위해 shift() 메서드를 사용했는데, 그렇게되면 그 뒤 요소들이 앞으로 한 칸 씩 당겨지는 O(N)의 시간복잡도를 매 반복마다 가지기 때문에 시간초과가 발생했다.

 

실패 코드 (오답)

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

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

const EMPTY = 0;
const WALL = 1;

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

let result = Infinity;

function solution() {
  bfs();

  console.log(result === Infinity ? -1 : result);
}

function bfs() {
  const queue = [[0, 0, 1, false]];
  const visited = Array.from({ length: N }, () => Array(M).fill(false));

  visited[0][0] = true;

  let queueIndex = 0;
  while (queueIndex < queue.length) {
    const [curRow, curCol, curCount, broken] = queue[queueIndex++];

    if (curRow === N - 1 && curCol === M - 1) {
      result = curCount;
      return;
    }

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      if (!isValid(nr, nc)) {
        continue;
      }
      if (visited[nr][nc]) {
        continue;
      }
      if (broken && map[nr][nc] === WALL) {
        continue;
      }

      visited[nr][nc] = true;

      if (map[nr][nc] === WALL && !broken) {
        queue.push([nr, nc, curCount + 1, true]);
      } else {
        queue.push([nr, nc, curCount + 1, broken]);
      }
    }
  }
}

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < M;
}

solution();

 

위에서 말했다시피, shift() 메서드가 문제였기 때문에 queue의 index를 나타내는 queueIndex라는 변수를 따로 뒀다.

하지만 약 15% 정도에서 틀렸다.

 

생각해보니 각 칸마다 벽을 부수고 도달했는지, 부수지 않고 도달했는지를 판단할 수 없었다.

위의 코드는 단순히, 한 번 벽을 부쉈으니까 다음엔 벽 못부셔~ 라는 로직일 뿐이었다.

그래서 visited 배열을 벽을 부수고 도달했는지, 부수지 않고 도달했는지를 따로 저장하도록 3차원 배열을 만들어서 해결했다.

 

성공 코드

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

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

const EMPTY = 0;
const WALL = 1;

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

function solution() {
  const result = bfs();

  console.log(result);
}

function bfs() {
  const queue = [[0, 0, 1, 0]];
  const visited = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => Array(2).fill(false))
  );

  visited[0][0][0] = true;

  let queueIndex = 0;
  while (queueIndex < queue.length) {
    const [curRow, curCol, curCount, broken] = queue[queueIndex++];

    if (curRow === N - 1 && curCol === M - 1) {
      return curCount;
    }

    for (let d = 0; d < 4; d++) {
      const nr = curRow + dr[d];
      const nc = curCol + dc[d];

      if (!isValid(nr, nc)) {
        continue;
      }

      // 갈 수 있는 곳 일 때,
      if (map[nr][nc] === EMPTY) {
        if (!visited[nr][nc][broken]) {
          queue.push([nr, nc, curCount + 1, broken]);
          visited[nr][nc][broken] = true;
        }
        // 벽이지만, 아직 벽을 부순 적이 없을 경우,
      } else if (map[nr][nc] === WALL && broken === 0) {
        if (!visited[nr][nc][1]) {
          queue.push([nr, nc, curCount + 1, 1]);
          visited[nr][nc][1] = true;
        }
      }
    }
  }

  return -1;
}

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < M;
}

solution();