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

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

2206번: 벽 부수고 이동하기

---

📌 작성한 코드 

//2206
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] = input.shift().split(" ").map(Number);
const board = [];

for (let i = 0; i < N; i++) {
    board.push(input[i].split(""));
}

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

const bfs = (tempMap) => {
    if (N - 1 === 0 && M - 1 === 0) return 1;
    const visited = Array.from({ length: N }, () => Array.from({ length: M }, () => [false, false]));
    const queue = [];
    queue.push([0, 0, 1, 0]);
    visited[0][0][0] = true;

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

        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 (!visited[nx][ny][isBroken] && tempMap[nx][ny] === "0") {
                queue.push([nx, ny, t + 1, isBroken]);
                visited[nx][ny][isBroken] = true;
            }
            if (!isBroken && tempMap[nx][ny] === "1") {
                queue.push([nx, ny, t + 1, 1]);
                visited[nx][ny][1] = true;
            }
            if (nx === N - 1 && ny === M - 1) return t + 1;
        }
    }

    return -1;
};

console.log(bfs(board));

 

📌 설명 

[1,1]에서 [N,M]까지 이동하는 최단 경로를 구하는 문제이다. 일반적인 bfs 문제처럼 보이지만, 해당 문제에서는 특별하게 더 빠른 경로를 위해서 1개의 벽을 부시는 것을 허용한다. => bfs + [특별한 조건 적용]이 필요한 문제

 

(1) 첫 시도 : 벽을 하나씩 0으로 변경하기

처음에는 단순히 벽들중 하나를 갈 수 있는 길로 변경하고(1->0), bfs를 돌리는 방법을 생각했었다. 그러나 이렇게 구현하니 메모리 초과가 발생하였다. 시간 복잡도와 공간 복잡도를 고려하지 않은 알고리즘이었다. 

 

N,M은 최대 1000까지 가능하고, 맵의 크기는 최대 1000 * 1000 = 1,000,000 (백만)까지 가능하다. 만약 맵이 전부 1로 채워져 있을 경우 백만번의 bfs를 돌아야 하고, 매 bfs마다 방문 배열을 생성하므로 백만 크기의 배열이 백만번 생성되어야 하는 것이다 -> 1,000,000^2 = 거의 1조. 메모리 초과가 안날래야 안날 수 없는 크기인 것이다. 그러므로 해당 방법은 사용 불가능하다. 

 

(2) 삼차원 방문 배열 사용하기

그렇다면 우리는 시간 복잡도와 공간 복잡도를 고려해서 bfs를 여러번 돌리지 않고 최단 거리를 구해야 한다. 그렇다면 우리는 bfs를 돌면서 동시에 벽을 부숴보는 선택을 할 수 있을 것이다. 사방을 확인하고, 해당 방향이 0이라면 그대로 방문하고, 1이라면 벽을 부수고 방문해보는 것이다. 그러나 우리는 벽을 딱 1번만 부술 수 있다. 그렇다면 현재 위치에서 다른 방향으로의 이동을 고려할 때 벽을 이미 부쉈는가? 아니면 아직 부술 수 있는 가를 알아야 한다. 이를 저장하기 위해 삼차원 배열을 사용할 것이다. 

 

삼차원 배열에는 `[x,y,벽 부서졌는지 여부]`를 저장할 것이고, bfs에서 사방을 확인할 때 이렇게 두가지 방법에 대한 경로를 모두 탐색할 것이다.

[1] (벽 부순지 여부 상관없이) 해당 위치에 방문한적이 없고, 해당 위치가 길(0)이라서 방문할 수 있으면 큐에 넣기

[2] 벽을 부수지 않은 상태에서 해당 위치에 방문한 적이 없고, 해당 위치의 벽(1) 부수고 방문할 예정이면 큐에 넣기

if (!visited[nx][ny][isBroken] && tempMap[nx][ny] === "0") { // [1]번
    queue.push([nx, ny, t + 1, isBroken]);
    visited[nx][ny][isBroken] = true;
}
if (!isBroken && tempMap[nx][ny] === "1") { // [2]번
    queue.push([nx, ny, t + 1, 1]);
    visited[nx][ny][1] = true;
}

 

만약 현재 벽이 부서진 상태라면 더이상 벽을 부술 수 없으므로 [2]는 불가능하고 [1]의 조건에 해당 하는 경우에 대한 방법만 고려하게 된다. 그래서 벽을 여러번 부시지 않고 딱 1번만 부수면서 최단 경로를 찾을 수 있는 것이다.

 

📌 참고

https://kscodebase.tistory.com/66

[bfs] 벽 부수고 이동하기 (백준 2206번)

문제를 해결한 후에 어떻게 설명하면 좋을까 고민하다가 보게 된 블로그인데, 해당 블로그에 첨부된 힌트 글이 굉장히 좋아서 해당 글을 같이 보면 좋을 것 같아서 공유해본다. 어째서 이런 방법으로 문제를 풀어야 하는지 그 이유에 대해 자세히 탐구하고 있다. 이번 문제 뿐만 아니라 다른 문제를 풀 때도 도움이 될 것 같다.

 

✅ 성공