[백준] 2206 벽 부수고 이동하기 - javascript

📌 문제

https://www.acmicpc.net/problem/2206

📌 풀이

class Node {
  constructor(x, y, wall, time) {
    this.x = x;
    this.y = y;
    this.wall = wall;
    this.time = time;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  push(x, y, wall, time) {
    let node = new Node(x, y, wall, time);
    if (this.size === 0) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }
  shift() {
    let temp = this.head;
    if (this.size === 0) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.size--;
    return temp;
  }
  length() {
    return this.size;
  }
}

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

const [N, M] = input.shift().split(' ').map(Number);
const arr = input.map((i) => i.trim().split('').map(Number));
const visited = Array.from({ length: N }, () => Array.from({ length: M }, () => Array.from({ length: 2 }, () => false)));
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

let queue = new Queue();
queue.push(0, 0, true, 1);
let ans = -1;
while (queue.length()) {
  let cur = queue.shift();
  const [x, y, canBreak, time] = [cur.x, cur.y, cur.wall, cur.time];
  if (x === N - 1 && y === M - 1) {
    ans = time;
    break;
  }

  if (visited[x][y][canBreak]) continue;
  visited[x][y][canBreak] = true;

  for (let i = 0; i < 4; i++) {
    let [nx, ny, ntime, nextCanBreak] = [x + dx[i], y + dy[i], time + 1, canBreak];
    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

    if (arr[nx][ny]) {
      if (nextCanBreak) nextCanBreak = false;
      else continue;
    }
    queue.push(nx, ny, nextCanBreak, ntime);
  }
}
console.log(ans);

✔ 알고리즘 : 구현 + BFS

✔ 기존의 bfs문제와 다른점은 벽을 부실수 있다는 조건때문에 visited 배열을 N * M의 2차원 배열이 아닌 벽을 부수고 N,M좌표로 가는 경우와 안부수고 가는 경우를 따져야 하기 때문에 3차원 배열로 visited처리를 해줘야 된다는 점이다.

const visited = Array.from({ length: N }, () => Array.from({ length: M }, () => Array.from({ length: 2 }, () => false)));

✔ 벽은 한번밖에 부시지 못하므로 4방향 탐색을 하면서 범위안에 있고 다음 좌표가 0인지 1인지에 따라서 처리해줘야 한다.

✔ 1인 경우 : 벽을 부술 수 있으면 (nextCanBreak = true) 탐색가능

if (arr[nx][ny]) {
  if (nextCanBreak) nextCanBreak = false;
  else continue;
}

✔ 0인 경우 : 무조건 탐색 가능

❗ 왜인지는 모르겠지만 배열로 queue를 사용하면 시간초과가 발생한다. 따라서 직접 큐를 구현함으로써 시간초과를 해결하였다.

✔ 난이도 : 백준 기준 골드 4