[백준] 2206번 : 벽 부수고 이동하기 (골드 Ⅳ) by node.js

▷ 문제 : 2206번 - 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

▷ 해결 날짜 : 2022.07.22
▷ 소요 시간 : 3시간
▷ 풀이 과정 :

이 문제는 내가 현재 풀 수 없는 문제이다.

타 회사의 코테 문제로 나왔던 비슷한 유형의 문제인데, 최단거리를 구하는 문제이며 벽을 "한 번" 부술 수 있다.

BFS의 응용인 것은 알겠는데, 도저히 접근하는 방법이 떠오르지 않아 혼자서는 풀 수 없었다.

 

일단 구글링의 도움을 받아 해결을 하였는데,

기본 틀은 일반적으로 BFS를 통해 최단거리를 구했던 구조와 동일하다.

 

그리고 이 문제의 핵심은 벽을 부술때와 부수지 않았을 때의 경우를 각각 체크해준다는 점에 있는데, 이를 위해 visited 배열을 3차원으로 처리하거나, 2차원 배열을 사용하되 방문하지 않음, 벽은 부수지 않음, 벽을 부숨 이렇게 3가지의 경우를 체크해주면 된다.

 

나 같은 경우에는 3차원 배열이 그나마 깔끔하기에 3차원 배열을 사용하였다.

그리고 벽은 단 한번만 부술 수 있고, 도달 점에 가장 먼저 도착하는 게 최단거리이기 때문에 도착 지점에서 break를 걸어주어 답을 구하면 된다.

 

이 정도만 인지하고 문제를 풀면 생각보다 쉽게 해결책을 낼 수 있으나, 문제는 이제 "메모리 초과"와 "시간 초과"이다.

일반적으로 queue.shift()를 사용하게 되면 "시간 초과"가 발생하며, 그렇다고 queue[i]를 통해 접근하면 "메모리 초과"가 발생한다.

 

그래서 아래 코드를 보면 알겠지만 Queue를 class로 직접 구현하여 사용하였다.

 

▷ 구현

let fs = require("fs");
let input = fs.readFileSync("./dev/stdin").toString().split("\n");

class Node {
  constructor(x, y, cnt, isBreak) {
    this.x = x;
    this.y = y;
    this.isBreak = isBreak;
    this.cnt = cnt;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  push(x, y, cnt, isBreak) {
    let node = new Node(x, y, cnt, isBreak);
    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;
  }
  get length() {
    return this.size;
  }
}

const ds = [
  [-1, 0],
  [1, 0],
  [0, 1],
  [0, -1],
];
const [N, M] = input.shift().split(" ").map(Number);
// visited[x][y][0/1] : 0 : 벽을 부수지 않음, 1 : 벽을 부숨
const visited = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => Array.from({ length: 2 }, () => 0))
);
const graph = [];
for (let i = 0; i < N; i++) {
  const isBreak = input[i].split("").map(Number);
  graph.push(isBreak);
}

let queue = new Queue();
queue.push(0, 0, 1, 0);
let answer = -1;
while (queue.length) {
  // isBreak는 현재 벽을 부순 상태인지 체크하는 변수
  let q = queue.shift();
  const [x, y, cnt, isBreak] = [q.x, q.y, q.cnt, q.isBreak];

  // 골 지점에 도달했을때 강제 브레이크 (가장 먼저 도착한게 최단거리기 때문이다.)
  if (x === N - 1 && y === M - 1) {
    answer = cnt;
    break;
  }

  // 방문한 적이 있는지 확인
  if (visited[x][y][isBreak]) continue;
  else visited[x][y][isBreak] = 1;

  // 4방향으로 이동
  for (let i = 0; i < 4; i++) {
    const xPos = x + ds[i][0];
    const yPos = y + ds[i][1];

    // 범위를 벗어났으면 패스
    if (xPos < 0 || yPos < 0 || xPos >= N || yPos >= M) continue;

    // 해당 지점이 벽인지 아닌지 확인
    // 벽일 경우 만약 부순적이 없다면 벽을 부수고, 부순적이 있다면 다시 되돌아간다.
    let nextIsBreak = isBreak;
    if (graph[xPos][yPos]) {
      if (!nextIsBreak) nextIsBreak = 1;
      else continue;
    }
    queue.push(xPos, yPos, cnt + 1, nextIsBreak);
  }
}

console.log(answer);

 

▷ 복기 :

너무 어렵다 진짜 그래도 새로운 문제 유형 뚫었으니 기분은 좋다.