문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제

예제 입력 1

6 4 1
0100
1110
1000
0000
0111
0000

예제 출력 1

15

예제 입력 2

6 4 2
0100
1110
1000
0000
0111
0000

예제 출력 2

9

예제 입력 3

4 4 3
0111
1111
1111
1110

예제 출력 3

-1

해결방법

기존의 최단거리 문제는 해당위치에서 동서남북 방향으로 아직 방문하지 않았다면 해당 노드를 방문하고 큐에 넣어 진행하는 방식이지만 이 문제에서는 벽을 깨부수는 경우가 추가되었다.

이 문제를 해결하기 위한 핵심포인트는 벽을 깨부순 상태를 각각 달리하는 것이다.
예를 들어 벽을 0개 부순 상태, 벽을 1개 부순 상태, 벽을 2개 부순 상태는 별개의 인격체를 가진다는 것이다. 즉, 벽의 개수마다 방문처리를 해줘야한다.

그래서 방문처리배열을 기존의 2차원 배열에서 3차원 배열로 변경시켜줘야한다.

하지만 한가지 더 문제가 생겼다. 큐에 다음 노드를 삽입하고 반복문을 돌다보면 메모리초과가 발생한다. 그 이유는 자바스크립트에는 큐가 내장되어있지 않아 일반 배열을 큐 처럼 사용하는데 이때 배열크기를 초과하기때문에 메모리가 초과가 발생했다. 이를 해결해 주기 위해서 클래스를 사용해 직접 큐를 구현해주었다.

const [[N, M, K], ...map] = `4 4 3
0111
1111
1111
1110`
  .toString()
  .trim()
  .split("\n")
  .map((el, idx) =>
    idx ? el.split("").map(Number) : el.split(" ").map(Number)
  );
//큐 규현
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.rear = null;
    this.length = 0;
  }

  isEmpty() {
    if (this.length === 0) return true;
    return false;
  }

  enqueue(data) {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return false;

    const data = this.head.data;
    this.head = this.head.next;
    this.length--;

    return data;
  }
}

const visited = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => new Array(K + 1).fill(0))
);

visited[0][0][0] = 1;
//큐 생성
const queue = new Queue();
queue.enqueue([0, 0, 0, 1]);
let idx = 0;
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

while (!queue.isEmpty()) {
  const [curRow, curCol, wall, step] = queue.dequeue();

  for (let i = 0; i < 4; i++) {
    const [nextRow, nextCol] = [curRow + dr[i], curCol + dc[i]];

    if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) continue;

    //벽이고 다음 벽까지 합쳐서 K개 이하이고 방문한 적 없음
    if (
      map[nextRow][nextCol] === 1 &&
      wall + 1 <= K &&
      visited[nextRow][nextCol][wall + 1] === 0
    ) {
      visited[nextRow][nextCol][wall + 1] = step + 1;
      queue.enqueue([nextRow, nextCol, wall + 1, step + 1]);
    }

    //벽이 아니고 방문한 적 없음
    if (map[nextRow][nextCol] === 0 && visited[nextRow][nextCol][wall] === 0) {
      visited[nextRow][nextCol][wall] = step + 1;
      queue.enqueue([nextRow, nextCol, wall, step + 1]);
    }
  }
}

//최소값 반환
let min = Number.MAX_SAFE_INTEGER;
for (let i = 0; i <= K; i++) {
  const step = visited[N - 1][M - 1][i];
  if (step === 0) continue;
  min = Math.min(min, step);
}
min === Number.MAX_SAFE_INTEGER ? console.log(-1) : console.log(min);