[JS] 백준 2206 : 벽 부수고 이동하기 - 그래프, 이론그래프, 탐색너비 우선 탐색

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

2206번: 벽 부수고 이동하기

 

 

📋풀이과정

1. 이동하는 중에 벽을 부셔야한다 -> 이 조건이 중요하다

2. 이동하는 중에 벽을 부수므로 BFS를 뻗어나갈 때 방문표시할 visited 배열을 3차원배열로 해야한다.

 -> 이유는 만약 가다가 벽을 부수게 된다면 새로운 방문 배열로 간다

 -> 새로운 방문배열은 벽을 부순 후의 방문 배열이다.

 -> 새로운 방문배열에서 새롭게 다시 BFS를 뻗어나간다 ( 즉 벽 부수기 전 왔던 길도 다시 돌아갈 수 있음)

 ->이렇게 하는 이유는 벽을 부수기 전과 부순 이후는 다르게 검사해야한다.

3. 위 그림에서 보여주듯이 벽을 부수면 arr[y][x][1]에 방문표시를 하고,

4. 벽을 부수지 않고 이동한다면 arr[y][x][0]에 방문표시를 하는 것이다.

5. 그래서 상하좌우의 방문을 검사할 때 이전에 벽을 부쉈는지 안부쉈는지 확인할 변수가 필요하다. -wall

6. queue에 값을 넣으면서 벽이 있어서 벽을 부쉈다면 wall이라는 변수를 0에서 1로 바꿔준다.

 ->왜 0에서 1일까?

 ->이는 우리가 3차원 배열을 arr[y][x][0], arr[y][x][1] 로 만들었기 때문이다.

7. 이때 만약 wall이라는 변수가 1이면 이전에 벽을 부쉈다는 의미로 넘어가야한다.

8. y와 x가 주어진 맵의 마지막 부분에 도달했다면 그 값을 출력해준다.

 

 

🤟내 제출

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

let [N, M] = input.shift().split(" ").map(Number);
let arr = [];
for (var i = 0; i < N; i++) {
  arr.push(input.shift().split("").map(Number));
}
let dx = [1, 0, 0, -1];
let dy = [0, 1, -1, 0];
let result = -1;

let queue = [];
let idx = 0;
let visited = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => Array.from({ length: 2 }, () => 0))
);

queue.push([0, 0, 1, 0]);
while (idx != queue.length) {
  let [y, x, len, wall] = queue[idx];
  if (y == N - 1 && x == M - 1) {
    result = len;
    break;
  }
  for (let i = 0; i < 4; i++) {
    let check = wall;
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
    if (visited[ny][nx][wall] == 1) continue;
    if (arr[ny][nx] == 1) {
      if (check == 0) check = 1;
      else continue;
    }
    visited[ny][nx][check] = 1;
    queue.push([ny, nx, len + 1, check]);
  }
  idx++;
}

console.log(result);

 

 

💢어려웠던 점

1. 3차원배열을 이용했어야하는 문제임을 파악하지 못했다.

->벽을 이동하는 중에 부숨으로써 시간이 단축된다.

->나는 벽의 좌표들을 배열에 저장하고, 그 벽들을 하나씩 허물고 BFS를 진행하면서 그 중 가장 최단거리를 뽑아냈다.

->출력은 잘 되었지만 시간초과가 났다.

->shift때문이라고 생각해서 idx를 이용해서 바꿨지만 그다음에는 메모리 초과가 났다.

틀린 코드

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

let [N, M] = input.shift().split(" ").map(Number);
let arr = [];
for (var i = 0; i < N; i++) {
  arr.push(input.shift().split("").map(Number));
}
let wall = [];
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (arr[i][j] == 1) {
      wall.push([i, j]);
    }
  }
}

let dx = [1, 0, 0, -1];
let dy = [0, 1, -1, 0];
let result = N * M;
let flag = false;
wall.forEach((tt) => {
  let [wy, wx] = tt;
  arr[wy][wx] = 0;
  let queue = [];
  let visited = Array.from({ length: N }, () => Array(M).fill(0));
  visited[0][0] = 1;
  queue.push([0, 0, 1]);
  while (queue.length) {
    let [y, x, len] = queue.shift();
    if (y == N - 1 && x == M - 1) {
      flag = true;
      result = Math.min(result, len);
      break;
    }
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx >= 0 && ny >= 0 && nx < M && ny < N && arr[ny][nx] == 0) {
        if (visited[ny][nx] == 0) {
          visited[ny][nx] = 1;
          queue.push([ny, nx, len + 1]);
        }
      }
    }
  }
  arr[wy][wx] = 1;
});
console.log(flag ? result : -1);

2. 시간초과 메모리 초과

기존에 코드를 진행하면서도 시간초과와 메모리 초과를 경험했다.

이유는 두가지였다.

 1. shift이용하면 시간초과

-정답코드에서 shift를 이용하면 시간초과가 난다.

2. idx로 바꿀 때 정확한 위치에 continue 추가

-시간초과를 해결하기위해 idx를 사용할 때 유의해야한다.

- idx로 바꾸면 if( visited[ny][nx][wall] ==1 ) continue; 의 위치를 잘 넣어줘야한다.

-적절하게 queue에 삽입되기전 끊어주지 않으면 메모리 초과가 난다.

아래와 같이 해도 상관없다

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

let [N, M] = input.shift().split(" ").map(Number);
let arr = [];
for (var i = 0; i < N; i++) {
  arr.push(input.shift().split("").map(Number));
}
let dx = [1, 0, 0, -1];
let dy = [0, 1, -1, 0];
let result = -1;

let queue = [];
let idx = 0;
let visited = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => Array.from({ length: 2 }, () => 0))
);
queue.push([0, 0, 1, 0]);
while (idx != queue.length) {
  let [y, x, len, wall] = queue[idx];
  if (y == N - 1 && x == M - 1) {
    result = len;
    break;
  }

  for (let i = 0; i < 4; i++) {
    let check = wall;
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx >= 0 && ny >= 0 && nx < M && ny < N && visited[ny][nx][wall] == 0) {
      if (arr[ny][nx] == 1) {
        if (check == 0) check = 1;
        else continue;
      }
      visited[ny][nx][wall] = 1;
      queue.push([ny, nx, len + 1, check]);
    }
  }
  idx++;
}

console.log(result);