[JavaScript/BFS] 백준 골드 3 : 14442 - 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

---

📌 작성한 코드 

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

const [N, M, K] = input.shift().split(" ").map(Number);
const board = input.map((str) => str.split(""));
const visited = Array.from({ length: N }, () => Array.from({ length: M }, () => new Array(K + 1).fill(false)));

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

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

class Queue {
    constructor() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val) {
        let newNode = new Node(val);
        if (!this.first) {
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }
    dequeue() {
        if (!this.first) return null;
        let temp = this.first;
        if (this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

const bfs = () => {
    if (N === 1 && M === 1) return 1;
    const queue = new Queue();
    queue.enqueue([0, 0, K, 1]);
    visited[0][0][K] = true;

    while (queue.size) {
        const [x, y, remain, count] = queue.dequeue();

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (remain > 0 && !visited[nx][ny][remain - 1] && board[nx][ny] === "1") {
                queue.enqueue([nx, ny, remain - 1, count + 1]);
                visited[nx][ny][remain - 1] = true;
            }
            if (!visited[nx][ny][remain] && board[nx][ny] === "0") {
                queue.enqueue([nx, ny, remain, count + 1]);
                visited[nx][ny][remain] = true;
            }
            if (nx === N - 1 && ny === M - 1) return count + 1;
        }
    }

    return -1;
};

console.log(bfs());

 

📌 풀이 

bfs를 이용해서 최단 거리를 구하는 문제이다. 단, k번 벽을 부술 수 있다는 특징이 있다. 

bfs 문제는 bfs의 구현에 특별한 조건을 달아서 구현시 해당 조건을 어떻게 구현하느냐에 따라 문제 해결 여부가 갈리게 된다. 

 

해당 문제는 백준의 벽 부수고 이동하기, 말이 되고픈 원숭이 문제의 해설을 보면 왜 이렇게 풀었는지 더 잘 이해할 수 있을 것이다.

https://youme016.tistory.com/334

[JavaScript] 백준 골드 3 : 2206 - 벽 부수고 이동하기

https://youme016.tistory.com/336

[JavaScript] 백준 골드 3 : 1600 - 말이 되고픈 원숭이

 

(1) 3차원 방문 배열을 사용하는 이유

우리는 k번 벽을 부술 수 있기 때문에, 해당 위치까지 왔을 때 벽을 n번 부수고 와서 앞으로의 이동에는 벽을 부술 수 있는 횟수가 k-n만큼 남았다는 것을 경로에 같이 기록해줘야 한다. 벽의 부수는 횟수와 부수는 순서(부순 위치)에 따라서 최단 경로가 달라질 수 있기 때문이다. (해당 위치까지 왔을 때 해당 방법이 최소 이동 횟수로 도달했다는 것이 보장되지 않기 때문이다). 그렇기 때문에 우리는 단순하게 해당 위치에 방문한 적이 있는지, 없는지 뿐만 아니라 해당 위치에 도달하는 동안 벽을 부순 횟수도 같이 기록해야 한다. 그래서 삼차원 배열을 이용해서 방문 기록을 저장하는 것이다. 

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

 

(2) 큐를 구현해야 하는 이유 

자바스크립트는 큐 자료 구조를 제공하고 있지 않기 때문에 보통 큐를 사용한 bfs 문제를 풀 때는 shift()를 해서 시간 복잡도를 증가시키기 보다는 idx를 사용해서 해당 idx를 이동 시키며 큐의 값을 확인하곤 했다.

let idx = 0;
while (queue.length > idx) { 
	const [x,y] = queue[idx++];
    ... }

 

그러나 우리는 이번에 큐에 저장할 데이터가 매우 많다. [x,y,남은 벽 부수기 횟수, 현재까지 이동 횟수] 이렇게 4가지나 된다.

이런 배열을 수도 없이 큐에 추가해 저장해야 하므로 결국 메모리 초과라는 문제가 발생한다. 그렇다고 shift를 사용하면 시간 초과가 발생한다. 이 문제는 우리의 구현 문제가 아니라 큐를 제공하고 있지 않기 때문이므로 큐를 구현해서 메모리 사용을 줄이는 수 밖에 없다.

// 간단 버전
class Node {
    constructor(val) {
        this.value = val;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val) {
        let newNode = new Node(val);
        if (!this.first) {
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }
    dequeue() {
        if (!this.first) return null;
        let temp = this.first;
        if (this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

 

✅ 성공