[JS] 백준 2206번 벽 부수고 이동하기

---

문제 링크

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

풀이 전략

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
(1, 1)과 (N, M)은 항상 0이라고 가정하자.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

코드 

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

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.rear = null;
        this.length = 0;
    }

    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 [n, m] = input.shift().split(" ").map(Number);
const possibleCases = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => Array.from({ length: 2 }, () => 0))
);
const arr = input.map((v) => v.split("").map(Number));

console.log(solution(0, 0, 0));

function solution(fx, fy, fw) {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    const queue = new Queue();
    possibleCases[fx][fy][fw] = 1;
    queue.enqueue([fx, fy, fw]);

    while (queue.length) {
        const [x, y, isBrakeWall] = queue.dequeue();

        if (x === n - 1 && y === m - 1) return possibleCases[x][y][isBrakeWall];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (possibleCases[nx][ny][isBrakeWall]) continue;
                if (arr[nx][ny] && !isBrakeWall) {
                    queue.enqueue([nx, ny, isBrakeWall + 1]);
                    possibleCases[nx][ny][isBrakeWall + 1] =
                        possibleCases[x][y][isBrakeWall] + 1;
                }
                if (!arr[nx][ny] && !possibleCases[nx][ny][isBrakeWall]) {
                    queue.enqueue([nx, ny, isBrakeWall]);
                    possibleCases[nx][ny][isBrakeWall] =
                        possibleCases[x][y][isBrakeWall] + 1;
                }
            }
        }
    }
    return -1;
}

회고

https://www.acmicpc.net/board/view/27386
https://kscodebase.tistory.com/66#comment12811239

이문제를 푸는데 많은 도움을 받은 글들이다. 이 문제에서 bfs가 왜 사용되어야 하고 어떻게 구성해야하는지 기본틀을 첫번째 링크에서 알 수 있었고 계속해서 풀다가 정답은 맞지만 메모리초과, 시간초과가 나는이유를 찾지 못하다가 
두번째 링크에서 이미 방문한적 있는 정점이면 continue하라는 if문을 보고 내 문제를 해결할 수 있었다. 
            
그리고 이 문제도 자바스크립트에 내장되어 있는 내장 배열 메서드로 구현하면 시간초과가 나기 때문에 index로 구현하거나 직접 클래스로 선언하여 구현해야한다. 꽤 시간이 걸렸지만 많은 것을 얻어갈 수 있는 문제였다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)